Re: Basically a sieve method, relation to quantum

From: Michael Brown (see_at_signature.below)
Date: 01/23/05 

Date: Sun, 23 Jan 2005 12:53:55 +1100

jstevh@msn.com wrote:
> Xcott Craver wrote:
>> <jstevh@msn.com> wrote:
>>>
>>> I get a sense that some of you don't get it, so let's say you take
>>> some RSA challenge number, and calculate j and T, and factor them,
>>> and then run them through the algorithm.
>>>
>>> My research indicates you have a 50% chance of factoring the number.
>>
>> If this is true, then why not run your algorithm on ALL of the
>> challenge numbers, and factor about half of them?
>>
>> If what you're saying is true, you could factor at least one
>> challenge number today.
>>
>
> Conceivably, yes, if I used some other program to factor T, since my
> current program just would in all likelihood fail to fully factor it,
> as I call it recursively to do all the factorizations, breaking down a
> number until it gets to something smaller than 200, at which point it
> uses a table of primes!
>
> Remember my method is *surrogate* factoring, which means you have to
> factor something!!!

For what it's worth, I cooked up a couple of ~64-bit primes (was a 104-bit
product, I forgot to set the uppermost bits). They weren't specially chosen
or even well-generated. I just used the rand() function to generate a binary
string. Their product was 17417537469613251264524569748998981537. "factor"
from:
http://www.asahi-net.or.jp/~KC2H-MSM/cn/
factored it in 33.26 seconds (1128714656609730623 * 15431302648208293919).
After a bit of trial and error, it turned out that it could factor the
product squared minus 16 in 3.26 seconds:
303370611505381579716912725262028356146608169452120680027239449463266882353
= 3* 3 * 71 * 307 * 2673397 * 84828952219129 * 8533686513259849 *
799079573776815674841701598797953

How do you get the original primes from the above factorisation? Or does j
have to be specially chosen? 

-- 
Michael Brown
www.emboss.co.nz : OOS/RSI software and more :)
Add michael@ to emboss.co.nz ---+--- My inbox is always open

Relevant Pages

  • Re: Basically a sieve method, relation to quantum
    ... > Xcott Craver wrote: ... then why not run your algorithm on ALL of the ... > as I call it recursively to do all the factorizations, ... How do you get the original primes from the above factorisation? ...
    (sci.math)
  • Re: Suggestions for double-hashing scheme
    ... i.e. the multiplicative group might be of size /2 if p is ... That's what my algorithm is for. ... > factorizations of N-1, which may or may not be fast. ... mathematical proof of primeness that it constructs is understandable. ...
    (comp.programming)
  • Re: Solving k^m = q mod N
    ... is less than N then you will take j factorizations. ... For my algorithm ... Can *anyone* even prove that it will always exit? ... I'm not playing in their league at all. ...
    (sci.math)
  • Re: Solving k^m = q mod N
    ... is less than N then you will take j factorizations. ... and that the poster's algorithm will exit as he expects? ... Can *anyone* even prove that it will always exit? ... any binary string is equally likely to occur as any other binary ...
    (sci.math)
  • Re: New way to factor? Yes!
    ... > your target number (while Pollard's Rho method I think does not). ... an algorithm that is pretty easy to understand. ... > algorithms from what I've just shown using factorizations of j and ... > And I call T the surrogate, and the method surrogate factoring. ...
    (sci.crypt)