[Cryptography] A new method to (partly) factorize RSA 250 and other large copmposite numbers

[Ray Dillinger]

What order you try factors in doesn't actually matter.  You can start
from just under the squareroot and work your way down, or you can start
from zero and work your way up.  And assuming that the factor has the
same number of digits as the squareroot, or one digit less, you won't
be checking any fewer factors, on average.

Using Euler's method to check for common factors with a very large
number made by multiplying many factors together is one of those ideas
that keeps coming up because it's clever, but doesn't help much.  And,
to the extent that it does help at all, there is already an equivalent
to it which is part of the General Number Field Sieve algorithm.

The very large composites you want to check for common factors against,
must be of a size that's hard to communicate relative to the number
you're trying to factor, and the sheer scale of the operations required
to do Euler's method, even on the first step, makes the operation as
hard as known methods of factoring.

I apologize for using a tricky phrase like "orders of magnitude more
orders of magnitude more digits" if English is not your first language.
Even most native English speakers would gloss over it as mathematical
jargon or, if they understood it, dismiss it as impossible hyperbole.

But please work through that phrase, because it is literally true and
you need to understand what it means to see what is wrong with this
idea.  That is the only "simple" phrase I can think of to that
accurately states the scale of the constructed composite you'd be
checking against for common factors, relative to the composite you're
trying to factor.

				Bear







On 08/19/2018 04:31 AM, Antje Wissmann wrote:
> Hallo cryptografers,
> 
>  
> 
> I’m searching for someone who may help me by writing a little program
> for factoring large composite numbers.
> 
>  
> 
> I’ve been into primes for a couple of years now and have discovered a
> structure that enables one to factorize composite numbers in a special
> way. It starts directly under the squareroot of a given integer and
> works backwords from that point through the possible factors. And it’s
> working _very_ fast at the beginning (while checking the highest
> possible factors) and is then slowing down constantly until it reaches
> the very small factors (like 101), where it is still working properly
> but it’s definitely to slow and not longer useful in a practical way.
> 
>  
> 
>  RSA 250 was the chosen number to describe the method using that integer
> as an example. It is known that the prime factors of RSA 250 are primes
> of the form 6n – 1, that is why the description of the method is basicly
> focused on this group of possible factors (but it also works for factors
> of the type 6n + 1 , slightly modified of course).
> 
>  
> 
> The “General Number Field Sieve” and its variations are the fastest
> methods for the factorization so far. Used as an alternative start the
> method I found should be _faster_ as the General Number Field Sieve – up
> to a certain point, of course (while checking the biggest factors).
> 
>  
> 
> Let us look at RSA 250 as an example to get an idea of the speed of this
> alternative approach:
> 
>  
> 
> RSA 250 is a number with 250 decimal digits. Using the method I’m
> talking about it’s possible to check the first group of
> 
> 20831160293131638348898886842852463138276835849237265490215514 factors
> (of the form 6n – 1)
> 
> with the result that non of them divides RSA 250. That proce­dure will
> take only a few minutes when calculated  _manually_ (like I have to do),
> checking that group of 2.08 * 10^61 factors in the first round. The next
> group of possible factors is a little bit smaller, so the whole thing
> starts slowing down step by step (as said at the beginning).
> 
>  
> 
> If one takes a much bigger number with 2500 decimal digits for example,
> the number of checked integers in the first group is _increasing_ – so
> the method becomes _faster_ than before (again: we’re looking only at
> the biggest possible factors at the moment). A randomly chosen integer
> of that size (not divisible by 2 and 3) will cost between 10 and 100
> times more calculating power for the first round (compared with RSA 250)
> but the method will check approximately 10^623 (!) possible factors at
> one time (that’s the average amount at the beginning).
> 
>  
> 
> If you think that this is fast than it’s worth programming (and if not:
> please let me know). Sadly I’m not capable to do so. The used structure
> and the used algorithm is easy to understand, so it should be easy to
> implement the whole thing, too. I’m searching for someone who is willing
> to do so and who can estimate (or calculate) the number of used
> _elementary operations_ as well, to compare this sieve with the other
> known methods.
> 
>  
> 
> Thank you for reading so far. If someone can help, please contact me.
> (Shall I post my e-mail-address or is there another way to get in contact?)
> 
>  
> 
> Please excuse any funny mistakes for English isn’t my natural language.
> 
>  
> 
> Kind regards
> 
>  
> 
> Helge Wißmann  (born in Germany, living in Switzerland)
> 
>  
> 
> PS: The mathematical background and the resulting structure for a
> program has been published as a little book a few days ago in Germany: 
> Ein Beitrag zur Faktorisierung von RSA 250       ISBN 978-3-7528-8619-1;  
> 
> Those who are interested in the matter may recieve a digital preprind 
> for free.
> 
> And I'll try to translate it into english, if nessecary.
> 
>  
> 
>  
> 
>  
> 
> 
> 
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography
> 

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20180819/b084e0e8/attachment.sig>