Re: Factoring problem, my assertion revisited
From: Tim Peters (tim.one_at_comcast.net)
Date: 02/08/05
- Next message: tomstdenis_at_gmail.com: "Re: Beginner fun challenge"
- Previous message: tomstdenis_at_gmail.com: "Re: New way to factor? Yes!"
- In reply to: ođin: "Re: Factoring problem, my assertion revisited"
- Next in thread: Rick Decker: "Re: Factoring problem, my assertion revisited"
- Reply: Rick Decker: "Re: Factoring problem, my assertion revisited"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Tue, 8 Feb 2005 14:16:03 -0500
[JSH]
>> Those of you who actually know about public key encryption know that
>> the two prime factors are carefully chosen to make the number hard to
>> factor, so the process of picking some j, to get M^2 - j^2 would
>> disrupt that choosing.
["ođin"]
> Nope. They are not carefully chosen.
Actually, they are.
> If that were true, then there would be a much smaller set to test
> against, making it easier to break into. The main thing is that the
> factors should be both large, but not close to each other in value.
And they shouldn't be close in value because, if they are, a particular
factoring method can exploit that. If the factors are p and q, you also
have to be careful that p/q isn't close to a simple fraction, that all of
p-1, p+1, q-1, and q+1 have at least one large prime factor, and so on. If
not, then other well-known factoring methods can crack p*q quickly.
Does that cut down the set of pairs to be searched? In absolute terms, yes,
by billions of billions of ... But in relative terms, p and q are so large
that weeding out known-to-be-bad pairs doesn't make a significant dent in
the search space.
> So it seems that your idea depends on a false assumption. But probably, T
> is no easier to factor than M.
T factors at once as (M+j)*(M-j). Both factors are about the size of M, but
j can be chosen in various special ways. For example, Décio Luiz Gazzoni
Filho pointed out that it's probably possible to find a j efficiently such
that M+j and M-j are both prime, and I noted quite a while ago that you
could, e.g., pick j s.t. M+j is the next larger power of 2 (so M+j factors
trivially, and then M and j are both odd so that 2 | M-j so we've peeled at
least 1 bit off the largest integer remaining to be factored).
But I can't make head or tail out of JSH's method after the point T is
factored. I can understand Rick Decker easily enough, but JSH keeps calling
him a liar (for no reason I can discern, apart from JSH's frequently
irrational online behavior); and JSH won't answer questions or even flesh
out how he expects to factor 15 as a concrete example -- he's his best
online buddy, and his worst online enemy.
- Next message: tomstdenis_at_gmail.com: "Re: Beginner fun challenge"
- Previous message: tomstdenis_at_gmail.com: "Re: New way to factor? Yes!"
- In reply to: ođin: "Re: Factoring problem, my assertion revisited"
- Next in thread: Rick Decker: "Re: Factoring problem, my assertion revisited"
- Reply: Rick Decker: "Re: Factoring problem, my assertion revisited"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
