mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2016-12-19, 06:29   #1
rxz7545
 
Dec 2016

28 Posts
Default RSA Key Factoring using Yafu

I am trying to use Yafu to factorize RSA Keys. One thing that surprises me is Yafu shows more than 2 factors even though RSA keys should have only 2 factors. Why is this so?

For example, when I factor the following no:

factor(1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139)


I get these as factors:

P2 = 11
P7 = 6698689
P8 = 18633149
P12 = 407893628797
P22 = 4702659209804290841741
P50 = 57813341690015577934703993485336625998708275892717
rxz7545 is offline   Reply With Quote
Old 2016-12-19, 07:07   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

3×23×83 Posts
Default

Quote:
Originally Posted by rxz7545 View Post
One thing that surprises me is Yafu shows more than 2 factors even though RSA keys should have only 2 factors. Why is this so?
RSA keys can have as many factors as the creator wants, but they won't be secure of course if they have many small factors. As to why you have so many factors in your number there could be many reasons. But most likely is perhaps it was created by bad software or a copy/paste error.
retina is online now   Reply With Quote
Old 2016-12-19, 07:44   #3
rxz7545
 
Dec 2016

2 Posts
Default

Quote:
Originally Posted by retina View Post
RSA keys can have as many factors as the creator wants, but they won't be secure of course if they have many small factors. As to why you have so many factors in your number there could be many reasons. But most likely is perhaps it was created by bad software or a copy/paste error.
But this key is from RSA Factoring Challenge: https://en.wikipedia.org/wiki/RSA_numbers#RSA-155
rxz7545 is offline   Reply With Quote
Old 2016-12-19, 07:54   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

3×23×83 Posts
Default

Quote:
Originally Posted by rxz7545 View Post
But this key is from RSA Factoring Challenge: https://en.wikipedia.org/wiki/RSA_numbers#RSA-155
Okay, it is RSA 100. And like I mentioned earlier, copy/paste error, because the factors are:
p=37975227936943673922808872755445627854565536638199
q=40094690950920881030683735292761468389214899724061
retina is online now   Reply With Quote
Old 2016-12-19, 07:54   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

53×73 Posts
Default

Quote:
Originally Posted by rxz7545 View Post
P2 = 11
P7 = 6698689
P8 = 18633149
P12 = 407893628797
P22 = 4702659209804290841741
P50 = 57813341690015577934703993485336625998708275892717
Multiply your factors together.
Compare to the original number...

...and you will find a copy-paste error (you lost one digit)
Code:
152260502792253336053561837813263742971806811496138068865790849458012296325892897654000350692006139
1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139

Last fiddled with by Batalov on 2016-12-19 at 08:02
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Running YAFU via Aliqueit doesn't find yafu.ini EdH YAFU 8 2018-03-14 17:22
YAFU using gmp-ecm with gpu johnadam74 YAFU 4 2017-05-22 16:25
Factoring 1024-bit number using Yafu Anyone YAFU 30 2015-09-01 13:25
Yafu crash after factoring this number al3ndaleeb YAFU 3 2015-05-30 19:54
Factoring a C155 with Yafu ivar YAFU 28 2012-02-06 12:37

All times are UTC. The time now is 04:21.

Mon Sep 21 04:21:40 UTC 2020 up 11 days, 1:32, 0 users, load averages: 1.58, 1.85, 1.76

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.