 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Condition on composite numbers easily factored (https://www.mersenneforum.org/showthread.php?t=24797)

 baih 2019-09-28 16:44

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 )

 R.D. Silverman 2019-09-28 19:28

[QUOTE=baih;526821]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 )[/QUOTE]

Purpose???

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

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

 baih 2019-09-28 20:02

purpose a large number c more than 1024BIT
with p and q also very large p and q ([B]private[/B] [B]key)[/B]

c is public
i can find pq from c

 Batalov 2019-09-28 22:37

[QUOTE=baih;526821]...and
(c +1)/4 = 1 Mod (p-1)
[/QUOTE]
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.

 baih 2019-09-28 22:46

yes i know

but step by step:wink:

 CRGreathouse 2019-09-29 00:35

[QUOTE=Batalov;526843]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.[/QUOTE]

Maybe the purpose is to be a backdoor for a cryptosystem where p and q are designed to be randomly selected? :ermm:

 axn 2019-09-29 02:29

[QUOTE=baih;526821]Can someone please propose a number ( c )[/QUOTE]

Sure. Here you go.
[CODE]retracting[/CODE]

 CRGreathouse 2019-09-29 04:46

:popcorn:

I would have chosen q to be around p^2. I wonder what axn chose. Perhaps we will see.

 axn 2019-09-29 04:53

[QUOTE=CRGreathouse;526864]:popcorn:

I would have chosen q to be around p^2. I wonder what axn chose. Perhaps we will see.[/QUOTE]

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
[/code]

 axn 2019-09-29 05:22

I had to retract the numbers as they did not properly satisfy OP's requirements.

 axn 2019-09-29 05:38

[CODE]3288315334013507348031117171885468096161021677564004034300356172248483753561621058705350647739894009\
5346045680550009445472595322983664958188142787148092914918061445039917611408596599725591252362294564\
1600699758076211854269675560352903000577560129603812320249402228524238334224780394198927618762027764\
4694175629521539892657010544312115079861771453079179141384844469970549673293813989678369426258452910\
3551493881299669360832439809441334130754552040177986894056672293223072559252965382679545203159671871\
1052801385883659044607163858197456954994787562252648007765822584016182739358104036624722033623683457\
3334375676353282746086370455038295247170962866302648507514375876708778979433419266589795636925613207\
4747459949682410108234198907723945838288102283178012219388623968160789028801889034265955398723460901\
5349542235839252138730727703428196783513008435899978778140980069771163397970731725281106467346639407\
481050648890548443151347[/CODE]
Try this. q = O(p^2)

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