Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Help with a factorisation, Please [Important]
Replies: 27   Last Post: Jan 26, 2014 9:33 AM

 Messages: [ Previous | Next ]
 David Bernier Posts: 3,892 Registered: 12/13/04
Re: Help with a factorisation, Please [Important]
Posted: Jan 24, 2014 10:53 PM

On 01/24/2014 09:22 PM, Port563 wrote:
> "Hlauk" <hlauk.h.bogart@gmail.com> wrote in message

>> On Friday, January 24, 2014 10:50:44 AM UTC-5, David Bernier wrote:
>
>>> 69176818182079702962583905305944091851396378426614231238000704281 *
>>> 68643130470496608225965397098921704892910199186048409746525386899
>>> =
>>> 47485133560063190433548259679204355907477810307482663990525310023\
>>> 91821388435849831808696657092215642611599144927466443608010614619
>>>

>> Your composite has prime factors that are close to it's square root.
>> Should it make it easier to factor?
>>
>> Dan

>
> Yes, assuming that the breaker does not only start its check on the
> smallest factor and work upwards, but also (or first) starts at
> the square root and works down.
>
> But David wasn't trying to make a good public key.
>
> If the non-trivial factors are p1, p2; p1 > p2;
> we have:
> p1 ~ 6.91768181820797E+64
> p2 ~ 6.86431304704966E+64
> (p1-p2)/2 ~ 2.66843855791553E+62
>
> So, as David said there was nothing "special" about his choice of composite,
> a very crude measure of the factorisation difficulty is to compare
> (p1-p2)/2 with p2; this ratio is < 0.4%.
>
> One where p1/p2 ~ 3, say, this ratio would be ~100%.
>
> [I am aware that primes thin out as one goes higher, so the two sieve
> approaches are working at very different prime densities. As I said, this
> difficulty measure is very crude]
>
>

If we call N the composite, then N =
68909974326288155594274651202432898372153288806331320492263045590^2 -
266843855791547368309254103511193479243089620282910745737658691^2

that is, N as a difference of two squares.

As you say , (p1-p2)/2 ~= 2.7e+62. This is Fermat's method.

I'm not sure it helps a whole lot here, though ...

< http://en.wikipedia.org/wiki/Fermat%27s_factorization_method > .

David Bernier

--

Date Subject Author
1/18/14 Daniel Joyce
1/18/14 Port563
1/18/14 Daniel Joyce
1/18/14 Daniel Joyce
1/18/14 Port563
1/18/14 David Bernier
1/18/14 Daniel Joyce
1/18/14 Port563
1/18/14 Daniel Joyce
1/18/14 Port563
1/18/14 Port563
1/18/14 Daniel Joyce
1/18/14 Daniel Joyce
1/19/14 Daniel Joyce
1/19/14 Port563
1/19/14 Daniel Joyce
1/24/14 David Bernier
1/24/14 Daniel Joyce
1/24/14 Port563
1/24/14 David Bernier
1/25/14 Port563
1/25/14 Port563
1/25/14 Daniel Joyce
1/25/14 Port563
1/25/14 Daniel Joyce
1/25/14 Port563
1/26/14 Daniel Joyce