mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-07-02, 12:58   #1
RomanM
 
Jun 2021

31 Posts
Default How to quick find x, x^4 mod N<sqrt(N)?

N-composite number with no known factorization.

How to quick find such x, x^4 mod N<sqrt(N)?

Regrgs,
Roman
RomanM is offline   Reply With Quote
Old 2021-07-02, 13:02   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5×13×23 Posts
Default

Quote:
Originally Posted by RomanM View Post
How to quick find such x, x^4 mod N<sqrt(N)?
Sometimes I like the easy problems (but we're different) :
any 0<=x<N^(1/8) do the job.
R. Gerbicz is offline   Reply With Quote
Old 2021-07-02, 13:06   #3
RomanM
 
Jun 2021

31 Posts
Default

))) very good point!! And how about x>N^(1/4)??
RomanM is offline   Reply With Quote
Old 2021-07-02, 13:14   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5·13·23 Posts
Default

Quote:
Originally Posted by RomanM View Post
))) very good point!! And how about x>N^(1/4)??
Take: N-N^(1/8)<x<=N
R. Gerbicz is offline   Reply With Quote
Old 2021-07-02, 13:30   #5
RomanM
 
Jun 2021

31 Posts
Default

Indeed a wise choise! Definitely, may be You know how to solve the problem also for non-trivial x values?
RomanM is offline   Reply With Quote
Old 2021-07-02, 15:04   #6
slandrum
 
Jan 2021
California

3448 Posts
Default

What do you mean by non-trivial?

x = kN +/- q where 0<=q<N^(1/8)

Is that non-trivial enough?
slandrum is offline   Reply With Quote
Old 2021-07-02, 15:22   #7
RomanM
 
Jun 2021

31 Posts
Default

N^(1/4)<x<N-N^(1/4)
RomanM is offline   Reply With Quote
Old 2021-07-03, 14:42   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3·1,669 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-07-05, 14:20   #9
RomanM
 
Jun 2021

31 Posts
Default

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<<A^2, so just drop a) A^2 and Ceil() here prevail! 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)<z<N-sqrt(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 2021-07-05 at 15:18 Reason: many logical typo
RomanM is offline   Reply With Quote
Old 2021-07-05, 15:28   #10
RomanM
 
Jun 2021

31 Posts
Default

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)<z<N-sqrt(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). ***
RomanM is offline   Reply With Quote
Old 2021-07-08, 15:56   #11
RomanM
 
Jun 2021

111112 Posts
Default

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<c, break()););
localprec(7);
z=(b/c/1.);
if(z<1,print(z," ",t));
);}
RomanM is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
NFS sqrt by hand henryzz Factoring 18 2010-09-26 00:55
127*Sqrt(62) XYYXF Math 2 2007-12-08 12:31
ggnfs sqrt problem hallstei Factoring 7 2007-05-01 12:51
SQRT Problem R.D. Silverman NFSNET Discussion 11 2006-07-20 17:04
P(n+1)<(sqrt(P(n))+1)^2 Crook Math 3 2005-10-26 21:29

All times are UTC. The time now is 22:46.


Tue Oct 26 22:46:05 UTC 2021 up 95 days, 17:15, 1 user, load averages: 1.34, 1.32, 1.22

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.