mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Condition on composite numbers easily factored (Challenger) (https://www.mersenneforum.org/showthread.php?t=24823)

 baih 2019-10-09 19:46

Condition on composite numbers easily factored (Challenger)

[SIZE=3][B]q prime numbre
[/B][/SIZE]
[SIZE=3][B]p prime numbre[/B][/SIZE]
[SIZE=3][B]and q>p[/B][/SIZE]
[SIZE=3][B]lets c = qp[/B][/SIZE]

[SIZE=3][B][COLOR=SeaGreen]e[/COLOR]= 2^p mod q[/B][/SIZE]

[SIZE=3][B]if we know [COLOR=SeaGreen]e[/COLOR] we can factore (c)[/B][/SIZE]

[SIZE=3][B]ok letz try with c and e[/B][/SIZE]

 R. Gerbicz 2019-10-10 11:14

With "a mod n" we denote the smallest non-negative residue modulo n.

We're given e=2^p mod q and calculate (in polynomial time) r=2^n mod n

What is r mod q ?

Easy: r mod q=(2^n mod n) mod q=2^n mod q=(2^q)^p mod q=2^p mod q=e (used Fermat's little theorem).

So we know that r mod q=e, hence r-e is divisible by q, so q | gcd(r-e,n), and if this is not n, then
we could factorize: because q=gcd(r-e,n) and with a division p=n/q.

The (only) hole in this proof is that (in rare cases) it is possible that n=gcd(r-e,n), for example this is the case for n=341.

To see that it is really working:

[CODE]
f(n,e)={r=lift(Mod(2,n)^n);d=gcd(r-e,n);return(d)}
p=nextprime(random(2^30));
q=nextprime(random(2^30));
n=p*q;e=lift(Mod(2,q)^p);
print([p,q]);
f(n,e)

(one possible output)
? [623981947, 805922797]
? %42 = 805922797
[/CODE]

ps. we have not used that q>p.

 All times are UTC. The time now is 19:10.