mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-10-09, 19:46   #1
baih
 
Jun 2019

118 Posts
Default Condition on composite numbers easily factored (Challenger)

q prime numbre

p prime numbre
and q>p
lets c = qp


e= 2^p mod q

if we know e we can factore (c)

ok letz try with c and e

Last fiddled with by baih on 2019-10-09 at 19:51
baih is offline   Reply With Quote
Old 2019-10-10, 11:14   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,327 Posts
Default

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
ps. we have not used that q>p.

Last fiddled with by R. Gerbicz on 2019-10-10 at 11:16 Reason: typo
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Condition on composite numbers easily factored baih Factoring 16 2019-09-29 15:48
Factoring composite Mersenne numbers using Pollard Rho jshort Factoring 9 2019-04-09 16:34
Devaraj numbers- necessary and sufficient condition devarajkandadai Number Theory Discussion Group 7 2017-09-23 02:58
Runs of factored numbers henryzz Factoring 8 2017-03-09 19:24
Factoring highly composite Mersenne numbers philmoore Factoring 21 2004-11-18 20:00

All times are UTC. The time now is 20:29.

Tue Mar 31 20:29:12 UTC 2020 up 6 days, 18:02, 1 user, load averages: 2.39, 1.81, 1.73

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.