mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-09-28, 16:44   #1
baih
 
baih's Avatar
 
Jun 2019

2×17 Posts
Default 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 )
baih is offline   Reply With Quote
Old 2019-09-28, 19:28   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by baih View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2019-09-28, 20:02   #3
baih
 
baih's Avatar
 
Jun 2019

2×17 Posts
Default

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
baih is offline   Reply With Quote
Old 2019-09-28, 22:37   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

25×7×41 Posts
Default

Quote:
Originally Posted by baih View Post
...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.
Batalov is offline   Reply With Quote
Old 2019-09-28, 22:46   #5
baih
 
baih's Avatar
 
Jun 2019

2216 Posts
Smile

yes i know

but step by step
baih is offline   Reply With Quote
Old 2019-09-29, 00:35   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×33×5×11 Posts
Default

Quote:
Originally Posted by Batalov View Post
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?
CRGreathouse is offline   Reply With Quote
Old 2019-09-29, 02:29   #7
axn
 
axn's Avatar
 
Jun 2003

2·5·479 Posts
Default

Quote:
Originally Posted by baih View Post
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
axn is offline   Reply With Quote
Old 2019-09-29, 04:46   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22·33·5·11 Posts
Default



I would have chosen q to be around p^2. I wonder what axn chose. Perhaps we will see.
CRGreathouse is offline   Reply With Quote
Old 2019-09-29, 04:53   #9
axn
 
axn's Avatar
 
Jun 2003

2·5·479 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post


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
axn is offline   Reply With Quote
Old 2019-09-29, 05:22   #10
axn
 
axn's Avatar
 
Jun 2003

2·5·479 Posts
Default

I had to retract the numbers as they did not properly satisfy OP's requirements.
axn is offline   Reply With Quote
Old 2019-09-29, 05:38   #11
axn
 
axn's Avatar
 
Jun 2003

112668 Posts
Default

Code:
3288315334013507348031117171885468096161021677564004034300356172248483753561621058705350647739894009\
5346045680550009445472595322983664958188142787148092914918061445039917611408596599725591252362294564\
1600699758076211854269675560352903000577560129603812320249402228524238334224780394198927618762027764\
4694175629521539892657010544312115079861771453079179141384844469970549673293813989678369426258452910\
3551493881299669360832439809441334130754552040177986894056672293223072559252965382679545203159671871\
1052801385883659044607163858197456954994787562252648007765822584016182739358104036624722033623683457\
3334375676353282746086370455038295247170962866302648507514375876708778979433419266589795636925613207\
4747459949682410108234198907723945838288102283178012219388623968160789028801889034265955398723460901\
5349542235839252138730727703428196783513008435899978778140980069771163397970731725281106467346639407\
481050648890548443151347
Try this. q = O(p^2)
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
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
2 holes in bizarre theorem about composite Mersenne Numbers wildrabbitt Math 120 2016-09-29 21:52
Factoring highly composite Mersenne numbers philmoore Factoring 21 2004-11-18 20:00

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

Sat Dec 5 12:19:34 UTC 2020 up 2 days, 8:30, 0 users, load averages: 1.59, 1.59, 1.71

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.