 mersenneforum.org How to quick find x, x^4 mod N
 Register FAQ Search Today's Posts Mark Forums Read  2021-07-02, 12:58 #1 RomanM   Jun 2021 2·32 Posts How to quick find x, x^4 mod N 2021-07-02, 13:02   #2
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

33·5·11 Posts Quote:
 Originally Posted by RomanM How to quick find such x, x^4 mod N
Sometimes I like the easy problems (but we're different) :
any 0<=x<N^(1/8) do the job.   2021-07-02, 13:06 #3 RomanM   Jun 2021 2·32 Posts ))) very good point!! And how about x>N^(1/4)??   2021-07-02, 13:14   #4
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

33·5·11 Posts Quote:
 Originally Posted by RomanM ))) very good point!! And how about x>N^(1/4)??
Take: N-N^(1/8)<x<=N   2021-07-02, 13:30 #5 RomanM   Jun 2021 2·32 Posts Indeed a wise choise! Definitely, may be You know how to solve the problem also for non-trivial x values?   2021-07-02, 15:04 #6 slandrum   Jan 2021 California 2·73 Posts What do you mean by non-trivial? x = kN +/- q where 0<=q 2021-07-02, 15:22 #7 RomanM   Jun 2021 100102 Posts N^(1/4) 2021-07-03, 14:42 #8 Dr Sardonicus   Feb 2017 Nowhere 464810 Posts There is a possibly-interesting variant of the question if the modulus N is a prime number: finding small quartic residues (mod N) [which are not themselves fourth powers], and having found one, find a fourth root (mod N). If N is prime, and N == 3 (mod 4), then every quadratic residue mod N is also a fourth power residue mod N. [Proof: Let x^2 == a (mod N), a =/= 0 (mod N). Since -1 is a quadratic non-residue (mod N), exactly one of x and -x is a quadratic residue (mod N), and its square roots mod N are fourth roots of a (mod N)]. In this case, there is also a simple way to find square roots (mod N). If a is a quadratic residue (mod N), then x = a^((N+1)/4) satisfies x^2 = a^(N+1)/2 = a^(N-1)/2 * a = +1*a = a (mod N). If N is prime, and N == 1 (mod 4), there is AFAIK no simple formula for square roots (mod N). However, it is fairly simple to test the quadratic character mod N using quadratic reciprocity. So when N is prime, and N == 1 (mod 4) it is probably fairly quick to find a couple of small primes p and q which are quadratic residues (mod N). It is then certain that at least one of p, q, and p*q is a fourth power residue (mod N). The question can be decided by evaluating Mod(p,N)^((N-1)/4) and, if this is Mod (-1, N), Mod(q,N)^((N-1)/4). I note that -1 is a fourth-power residue (mod N) when N is prime and N == 1 (mod 8). I have no idea what has actually been proven about how small quartic residues (mod N) can be when N is prime and N == 1 (mod 4). I believe there are conditional estimates which depend on unproven results. When N is prime, there are functions that will find modular fourth roots. For example, factormod(x^4 - a, N), or y = sqrt(Mod(a, N)), followed by sqrt(Mod(y, N)) or sqrt(Mod(-y, N)). These functions will NOT work if N is composite. I also have no idea about results concerning the smallness of quartic (or even quadratic) residues modulo N when N is composite. I note that, if N is the sum of two relatively prime squares, there is a solution of w^2 + 1 == 0 (mod N) so that, if x^4 == a (mod N), then (w*x)^4 == a (mod N) also.   2021-07-05, 14:20 #9 RomanM   Jun 2021 2×32 Posts Life is easy when N is prime). Lets step down, to quadratic. Apart from looking for some k in t=sqrt(k*N) when t is close to integer number; use continued fractions or sieve some set of polynomials, we can do something more wierd. Let t^2==a mod N so replace t=A-y; (A-y)^2==a mod N A^2-2*A*y-y^2==a mod N. Ok. Let B==A^2 mod N; So B-2*A*y -y^2==a mod N. or -y^2-2*A*y+B-a==0 mod N. -> y=A+/-sqrt(A^2-B+a) y is not integer? Whatever, make him integer y=A+/-ceil(sqrt(A^2-B+a)). Variable a is unknown? a< 2021-07-05, 15:28 #10 RomanM   Jun 2021 2·32 Posts I do Wrong edit! In the last sentence, not y but t instead. t=A-y=-/+ceil(sqrt(A^2-B))=-/+ceil(sqrt(A^2+Mod(A^2,N))) And now, let A==Mod(z^2,N). Let sqrt(N) 2021-07-08, 15:56 #11 RomanM   Jun 2021 2·32 Posts Pari/GP code Code: `\p350 {p=233108530344407544527637656910680524145619812480305449042948611968495918245135782867888369318577116418213919268572658314913060672626911354027609793166341626693946596196427744273886601876896313468704059066746903123910748277606548649151920812699309766587514735456594993207; c=ceil(sqrt(p)); for(n=1,p, u=c+n; \\"guess" values b=lift(Mod(u^2,p)); a=lift(Mod(b^2,p)); for(y=1,250, \\most interesting part, 250 -dummy number for speed purpose, ~ 150-1800 for this size of p t=ceil((b^2-a)^(1/2)); b=lift(Mod(t^2,p)); a=lift(Mod(b^2,p)); if(b Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post henryzz Factoring 18 2010-09-26 00:55 XYYXF Math 2 2007-12-08 12:31 hallstei Factoring 7 2007-05-01 12:51 R.D. Silverman NFSNET Discussion 11 2006-07-20 17:04 Crook Math 3 2005-10-26 21:29

All times are UTC. The time now is 17:58.

Fri Jul 23 17:58:13 UTC 2021 up 12:27, 1 user, load averages: 2.71, 3.09, 3.33