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

[RomanM]

N-composite number with no known factorization.

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

Regrgs,
Roman

[R. Gerbicz]

Originally Posted by RomanM

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.

[RomanM]

))) very good point!! And how about x>N^(1/4)??

[R. Gerbicz]

Originally Posted by RomanM

))) very good point!! And how about x>N^(1/4)??

Take: N-N^(1/8)<x<=N

[RomanM]

Indeed a wise choise! Definitely, may be You know how to solve the problem also for non-trivial x values?

[slandrum]

What do you mean by non-trivial?

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

Is that non-trivial enough?

[RomanM]

N^(1/4)<x<N-N^(1/4)

[Dr Sardonicus]

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.

[RomanM]

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.

[RomanM]

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]

Pari/GP 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));
);}