20190928, 16:44  #1 
Jun 2019
2·17 Posts 
Condition on composite numbers easily factored
Choose two large distinct prime numbers p and q
p = prime q = prime Compute c=pq such that: c=3 Mod 4 and (c +1)/4) = 1 Mod (p1) there exist a Quick way of finding p and q from c Can someone please propose a number ( c ) 
20190928, 19:28  #2  
Nov 2003
2^{2}·5·373 Posts 
Quote:
Examples are easy to find. Infinitely many, in fact. Let c = 3q, q = 1 mod 8. Try e.g. c = 51 

20190928, 20:02  #3 
Jun 2019
42_{8} Posts 
purpose a large number c more than 1024BIT
with p and q also very large p and q (private key) c is public i can find pq from c Last fiddled with by baih on 20190928 at 20:13 
20190928, 22:37  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·4,729 Posts 

20190928, 22:46  #5 
Jun 2019
2×17 Posts 
yes i know
but step by step 
20190929, 00:35  #6 
Aug 2006
3×1,993 Posts 
Maybe the purpose is to be a backdoor for a cryptosystem where p and q are designed to be randomly selected?

20190929, 02:29  #7 
Jun 2003
3·1,669 Posts 
Sure. Here you go.
Code:
retracting Last fiddled with by axn on 20190929 at 05:22 
20190929, 04:46  #8 
Aug 2006
3×1,993 Posts 
I would have chosen q to be around p^2. I wonder what axn chose. Perhaps we will see. 
20190929, 04:53  #9  
Jun 2003
5007_{10} Posts 
Quote:
I'm counting on OP being able to factor the number. If not, we may never know the factorization, as I did not record the p, q values. EDIT: q = O(p^2) Code:
retracting Last fiddled with by axn on 20190929 at 05:21 

20190929, 05:22  #10 
Jun 2003
3×1,669 Posts 
I had to retract the numbers as they did not properly satisfy OP's requirements.

20190929, 05:38  #11 
Jun 2003
3×1,669 Posts 
Code:
3288315334013507348031117171885468096161021677564004034300356172248483753561621058705350647739894009\ 5346045680550009445472595322983664958188142787148092914918061445039917611408596599725591252362294564\ 1600699758076211854269675560352903000577560129603812320249402228524238334224780394198927618762027764\ 4694175629521539892657010544312115079861771453079179141384844469970549673293813989678369426258452910\ 3551493881299669360832439809441334130754552040177986894056672293223072559252965382679545203159671871\ 1052801385883659044607163858197456954994787562252648007765822584016182739358104036624722033623683457\ 3334375676353282746086370455038295247170962866302648507514375876708778979433419266589795636925613207\ 4747459949682410108234198907723945838288102283178012219388623968160789028801889034265955398723460901\ 5349542235839252138730727703428196783513008435899978778140980069771163397970731725281106467346639407\ 481050648890548443151347 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring composite Mersenne numbers using Pollard Rho  jshort  Factoring  9  20190409 16:34 
Devaraj numbers necessary and sufficient condition  devarajkandadai  Number Theory Discussion Group  7  20170923 02:58 
Runs of factored numbers  henryzz  Factoring  8  20170309 19:24 
2 holes in bizarre theorem about composite Mersenne Numbers  wildrabbitt  Math  120  20160929 21:52 
Factoring highly composite Mersenne numbers  philmoore  Factoring  21  20041118 20:00 