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)

 CRGreathouse 2019-09-29 06:22

This is the test code I used while composing the above posts to generate numbers of the OP's form; I wonder if it's similar to your code, axn?
[code]baih(N,P=N\3)=
{
my(p,lower,upper,k,q);
if(P>=N/2,error("Need p small"));
while(p%3<2,
p=randomprime([2^(P-1),2^P-1])
);
lower=ceil((2^(N-1)/p-3)/(p-1));
upper=(2^N\p-3)\(p-1);
while(q<1,
k=random(upper-lower)+lower;
q=k*(p-1)+3;
if(p*q%4==1||!ispseudoprime(q),q=0)
);
\\print(p);
p*q;
}
baih(3068)[/code]

 R. Gerbicz 2019-09-29 10:17

[QUOTE=axn;526871]
Try this. q = O(p^2)[/QUOTE]

Good challenge. Solved:
[CODE]
n=3288315334013507348031117171885468096161021677564004034300356172248483753561621058705350647739894009\
5346045680550009445472595322983664958188142787148092914918061445039917611408596599725591252362294564\
1600699758076211854269675560352903000577560129603812320249402228524238334224780394198927618762027764\
4694175629521539892657010544312115079861771453079179141384844469970549673293813989678369426258452910\
3551493881299669360832439809441334130754552040177986894056672293223072559252965382679545203159671871\
1052801385883659044607163858197456954994787562252648007765822584016182739358104036624722033623683457\
3334375676353282746086370455038295247170962866302648507514375876708778979433419266589795636925613207\
4747459949682410108234198907723945838288102283178012219388623968160789028801889034265955398723460901\
5349542235839252138730727703428196783513008435899978778140980069771163397970731725281106467346639407\
481050648890548443151347;

p=484605015374629056777963894537847106303895551675266313154360900707104424961427719036266452196533774\
52921936399517882322789881804586540944802829882322554400675112952961990074662282674675063947229415372\
10158614848604710460460300049181316857625972449622618772532492044500653582851152895649758081518411705\
6344899;
q=678555778353106856699471351544625270538870277275101480850221325370922821493334863046535648959050812\
25688605158423860427793393677368543359664716921597907268575312832766558132199830099232360905729404728\
99121337787838935076965193459155301627652246520120302228518250201648597012572946836549688528687425909\
44431888146970279878990658770601477218446643121167732647451536410730645312792077195198632467755596788\
25155503616310435258635806796447200837691193982379038095497921562247764105338407437089023151285738935\
17162015165055647773150505612736034197993659591091727613875121131926185630357234439967667412188642741\
148076798353;

n==p*q
%42 = 1
[/CODE]

 axn 2019-09-29 12:35

[QUOTE=CRGreathouse;526873]This is the test code I used while composing the above posts to generate numbers of the OP's form; I wonder if it's similar to your code, axn?
[/QUOTE]
Similar-ish, but less sophisticated. I hardcoded the sizes, and didn't bother with getting exact bit-lengths (so randomprime(2^1024) and random(2^2048)). Also for q, I started at random point and walked along an AP until an appropriate prime is found.

The only additional thing is the use of setrand.

 axn 2019-09-29 12:37

[QUOTE=R. Gerbicz;526879]Good challenge. Solved:
[/QUOTE]
:tu:

If you don't mind, what is the procedure?

I wonder if there is a family of similar conditions with which you can generate backdoored keys.

 baih 2019-09-29 15:05

[B]my solution are :qp =c
[/B]

[B]lets n is integer
[/B]
[B]e= (c+1)/4
[/B]
[B]s= n^e Mod c[/B]

[B]q= gcd(s-n,c)[/B]

[code]gcd(328831533401350734803111717188546809616102167756400403430035617224848375356162105870535064773989400953460456805500094454725953229836649581881427871480929149180614450399176114085965997255912523622945641600699758076211854269675560352903000577560129603812320249402228524238334224780394198927618762027764469417562952153989265701054431211507986177145307917914138484446997054967329381398967836942625845291035514938812996693608324398094413341307545520401779868940566722932230725592529653826795452031596718711052801385883659044607163858197456954994787562252648007765822584016182739358104036624722033623683457333437567635328274608637045503829524717096286630264850751437587670877897943341926658979563692561320747474599496824101082341989077239458382881022831780122193886239681607890288018890342659553987234609015349542235839252138730727703428196783513008435899978778140980069771163397970731725281106467346639407481050648890548443151347,33044430344567968457504390023730807700313470204127206103541738009757190061479952532666748417160803343549369591197775495859904337324192484080277708616305115571121880098481299055289260814667885642311554608842472462733334431317525082158702950796446483597745583328368895423573229578085998903425664004102550943684031377722419489648041589886974882817389337884568062324779444848203311395820530527814776447027532071511471572577892574608732728121724263102797210907168796982692953052763795367557134923837558068441166143485009803333253526113177756420178435576304830147949361380748235159254432926482497724084258840911722885237709628903306000933805702588271038163052264047981072345113780656741415339127876436623493274377738582532331423336092170940538472743424073894604109693078215734638692617988656076012724887785585490772500772435031723175876509289016224044113157928408771933675849061252766798346330233372053354515046214836702864157330)
48460501537462905677796389453784710630389555167526631315436090070710442496142771903626645219653377452921936399517882322789881804586540944802829882322554400675112952961990074662282674675063947229415372101586148486047104604603000491813168576259724496226187725324920445006535828511528956497580815184117056344899L[/code]

 R. Gerbicz 2019-09-29 15:48

[QUOTE=baih;526898][B]my solution are :qp =c
[/B]

[B]lets n is integer
[/B]
[B]e= (c+1)/4
[/B]
[B]s= n^e Mod c[/B]

[B]q= gcd(s-n,c)[/B]

Yes, more detail:
If n=p*q, and (n+1)/4==1 mod (p-1) then
(p-1) | e=(n-3)/4 with Fermat (for every b)
b^e-1 is divisible by p so p|gcd(b^e-1,n) and in general it is in fact p (and not n).

So (partial) factorization is easy when we know p|n and n mod (p-1).
Say we know that n==r/s mod (p-1) for tiny r,s (in solution just try all r,s pair).

 All times are UTC. The time now is 16:59.