mersenneforum.org Condition on composite numbers easily factored (Challenger)
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2019-10-09, 19:46 #1 baih     Jun 2019 2×17 Posts 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
 2019-10-10, 11:14 #2 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 57716 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post baih Factoring 16 2019-09-29 15:48 jshort Factoring 9 2019-04-09 16:34 devarajkandadai Number Theory Discussion Group 7 2017-09-23 02:58 henryzz Factoring 8 2017-03-09 19:24 philmoore Factoring 21 2004-11-18 20:00

All times are UTC. The time now is 23:50.

Tue Sep 29 23:50:18 UTC 2020 up 19 days, 21:01, 0 users, load averages: 1.59, 1.50, 1.46