mersenneforum.org Condition on composite numbers easily factored
 Register FAQ Search Today's Posts Mark Forums Read

 2019-09-28, 16:44 #1 baih   Jun 2019 118 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 (p-1) there exist a Quick way of finding p and q from c Can someone please propose a number ( c )
2019-09-28, 19:28   #2
R.D. Silverman

Nov 2003

25·233 Posts

Quote:
 Originally Posted by baih 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 (p-1) there exist a Quick way of finding p and q from c Can someone please propose a number ( c )
Purpose???

Examples are easy to find. Infinitely many, in fact.

Let c = 3q, q = 1 mod 8. Try e.g. c = 51

 2019-09-28, 20:02 #3 baih   Jun 2019 118 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 2019-09-28 at 20:13
2019-09-28, 22:37   #4
Batalov

"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

13·17·41 Posts

Quote:
 Originally Posted by baih ...and (c +1)/4 = 1 Mod (p-1)
This has no generality.
This means that q = 3 Mod (p-1). Which is a very poor choice of q tightly tied to p.
Even if you can solve it, it is of no practical interest. In ciphers, p and q will never be chosen like that.

 2019-09-28, 22:46 #5 baih   Jun 2019 916 Posts yes i know but step by step
2019-09-29, 00:35   #6
CRGreathouse

Aug 2006

2×3×977 Posts

Quote:
 Originally Posted by Batalov This has no generality. This means that q = 3 Mod (p-1). Which is a very poor choice of q tightly tied to p. Even if you can solve it, it is of no practical interest. In ciphers, p and q will never be chosen like that.
Maybe the purpose is to be a backdoor for a cryptosystem where p and q are designed to be randomly selected?

2019-09-29, 02:29   #7
axn

Jun 2003

41·113 Posts

Quote:
 Originally Posted by baih Can someone please propose a number ( c )
Sure. Here you go.
Code:
retracting

Last fiddled with by axn on 2019-09-29 at 05:22

 2019-09-29, 04:46 #8 CRGreathouse     Aug 2006 586210 Posts I would have chosen q to be around p^2. I wonder what axn chose. Perhaps we will see.
2019-09-29, 04:53   #9
axn

Jun 2003

41·113 Posts

Quote:
 Originally Posted by CRGreathouse I would have chosen q to be around p^2. I wonder what axn chose. Perhaps we will see.
q = O(p). Should the need arise, I can do your suggestion.

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 2019-09-29 at 05:21

 2019-09-29, 05:22 #10 axn     Jun 2003 41·113 Posts I had to retract the numbers as they did not properly satisfy OP's requirements.
 2019-09-29, 05:38 #11 axn     Jun 2003 41·113 Posts Code: 3288315334013507348031117171885468096161021677564004034300356172248483753561621058705350647739894009\ 5346045680550009445472595322983664958188142787148092914918061445039917611408596599725591252362294564\ 1600699758076211854269675560352903000577560129603812320249402228524238334224780394198927618762027764\ 4694175629521539892657010544312115079861771453079179141384844469970549673293813989678369426258452910\ 3551493881299669360832439809441334130754552040177986894056672293223072559252965382679545203159671871\ 1052801385883659044607163858197456954994787562252648007765822584016182739358104036624722033623683457\ 3334375676353282746086370455038295247170962866302648507514375876708778979433419266589795636925613207\ 4747459949682410108234198907723945838288102283178012219388623968160789028801889034265955398723460901\ 5349542235839252138730727703428196783513008435899978778140980069771163397970731725281106467346639407\ 481050648890548443151347 Try this. q = O(p^2)

 Similar Threads Thread Thread Starter Forum Replies Last Post 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 wildrabbitt Math 120 2016-09-29 21:52 philmoore Factoring 21 2004-11-18 20:00

All times are UTC. The time now is 11:33.

Sat Jul 11 11:33:33 UTC 2020 up 108 days, 9:06, 0 users, load averages: 1.38, 1.19, 1.20