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 31 Posts How to quick find x, x^4 mod N
2021-07-02, 13:02   #2
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·32·83 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 31 Posts ))) very good point!! And how about x>N^(1/4)??
2021-07-02, 13:14   #4
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

101110101102 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 1F16 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 DC16 Posts What do you mean by non-trivial? x = kN +/- q where 0<=q
 2021-07-02, 15:22 #7 RomanM   Jun 2021 31 Posts N^(1/4)
 2021-07-03, 14:42 #8 Dr Sardonicus     Feb 2017 Nowhere 116028 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 31 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 3110 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 31 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

 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 20:39.

Sat Oct 23 20:39:57 UTC 2021 up 92 days, 15:08, 0 users, load averages: 1.43, 1.25, 1.21