20210702, 12:58  #1 
Jun 2021
31 Posts 
How to quick find x, x^4 mod N<sqrt(N)?
Ncomposite number with no known factorization.
How to quick find such x, x^4 mod N<sqrt(N)? Regrgs, Roman 
20210702, 13:02  #2 
"Robert Gerbicz"
Oct 2005
Hungary
2·3^{2}·83 Posts 

20210702, 13:06  #3 
Jun 2021
31 Posts 
))) very good point!! And how about x>N^(1/4)??

20210702, 13:14  #4 
"Robert Gerbicz"
Oct 2005
Hungary
10111010110_{2} Posts 

20210702, 13:30  #5 
Jun 2021
1F_{16} Posts 
Indeed a wise choise! Definitely, may be You know how to solve the problem also for nontrivial x values?

20210702, 15:04  #6 
Jan 2021
California
DC_{16} Posts 
What do you mean by nontrivial?
x = kN +/ q where 0<=q<N^(1/8) Is that nontrivial enough? 
20210702, 15:22  #7 
Jun 2021
31 Posts 
N^(1/4)<x<NN^(1/4)

20210703, 14:42  #8 
Feb 2017
Nowhere
11602_{8} Posts 
There is a possiblyinteresting 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 nonresidue (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^(N1)/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)^((N1)/4) and, if this is Mod (1, N), Mod(q,N)^((N1)/4). I note that 1 is a fourthpower 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. 
20210705, 14:20  #9 
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=Ay; (Ay)^2==a mod N A^22*A*yy^2==a mod N. Ok. Let B==A^2 mod N;
So B2*A*y y^2==a mod N. or y^22*A*y+Ba==0 mod N. > y=A+/sqrt(A^2B+a) y is not integer? Whatever, make him integer y=A+/ceil(sqrt(A^2B+a)). Variable a is unknown? a<<A^2, so just drop a) A^2 and Ceil() here prevail! t=Ay=/+ceil(sqrt(A^2B))=/+ceil(sqrt(A^2+Mod(A^2,N))) And now, let A==Mod(z^2,N). Let sqrt(N)<z<Nsqrt(N). Once we compute y, we can let z=y and go to cycle! Watch my hands, still no cheating! This cycle frequently converging to y=0, or, one step before for y^2 mod N<sqrt(N). As far I know, there is a new heuristic for obtain sub sqrt residuals. Last fiddled with by RomanM on 20210705 at 15:18 Reason: many logical typo 
20210705, 15:28  #10 
Jun 2021
31_{10} Posts 
I do Wrong edit! In the last sentence, not y but t instead.
t=Ay=/+ceil(sqrt(A^2B))=/+ceil(sqrt(A^2+Mod(A^2,N))) And now, let A==Mod(z^2,N). Let sqrt(N)<z<Nsqrt(N). Once we compute t, we can let z=t and go to cycle! *** This cycle frequently converging to t=0, or, one step before for t^2 mod N<sqrt(N). *** 
20210708, 15:56  #11 
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, ~ 1501800 for this size of p t=ceil((b^2a)^(1/2)); b=lift(Mod(t^2,p)); a=lift(Mod(b^2,p)); if(b<c, break());); localprec(7); z=(b/c/1.); if(z<1,print(z," ",t)); );} 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
NFS sqrt by hand  henryzz  Factoring  18  20100926 00:55 
127*Sqrt(62)  XYYXF  Math  2  20071208 12:31 
ggnfs sqrt problem  hallstei  Factoring  7  20070501 12:51 
SQRT Problem  R.D. Silverman  NFSNET Discussion  11  20060720 17:04 
P(n+1)<(sqrt(P(n))+1)^2  Crook  Math  3  20051026 21:29 