Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
David Bernier

Posts: 3,317
Registered: 12/13/04
Re: Help with a factorisation, Please [Important]
Posted: Jan 18, 2014 2:55 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On 01/18/2014 01:27 PM, Port563 wrote:
> "Hlauk" <hlauk.h.bogart@gmail.com> wrote...
>> On Saturday, January 18, 2014 1:59:51 AM UTC-5, Port563 wrote:
>>> "Hlauk" <hlauk.h.bogart@gmail.com> wrote...
>>>
>>>
>>>
>>> 47485133560063190433548259679204355907477810307482663990525310023918
>>>
>>> 21388435849831808696657092215642611599144927466443608010614619
>>>
>>>
>>>
>>> ratio 1.25
>>>
>>>
>>>
>>> First (40) probable prime pairs for your composite.
>>>
>>>
>>>
>>> 61634492654722608941290260942255029432493581352934302103639605649
>>>
>>> 77043115818403261176612826177818672838794518722182177510519246611
>>>
>>> 61634492654722608941290260942255029432493581352934302103639655881
>>>
>>> 77043115818403261176612826177818672838794518722182177510519183821
>>>
>>> 61634492654722608941290260942255029432493581352934302103639660153
>>>
>>> 77043115818403261176612826177818672838794518722182177510519178481
>>>
>>> 61634492654722608941290260942255029432493581352934302103639696033
>>>
>>> 77043115818403261176612826177818672838794518722182177510519133631
>>>
>>> 61634492654722608941290260942255029432493581352934302103639705033
>>>
>>> 77043115818403261176612826177818672838794518722182177510519122381
>>>
>>> 61634492654722608941290260942255029432493581352934302103639731937
>>>
>>> 77043115818403261176612826177818672838794518722182177510519088751
>>>
>>> 61634492654722608941290260942255029432493581352934302103639808593
>>>
>>> 77043115818403261176612826177818672838794518722182177510518992931
>>>
>>> 61634492654722608941290260942255029432493581352934302103639897393
>>>
>>> 77043115818403261176612826177818672838794518722182177510518881931
>>>
>>> 61634492654722608941290260942255029432493581352934302103639998673
>>>
>>> 77043115818403261176612826177818672838794518722182177510518755331
>>>
>>> 61634492654722608941290260942255029432493581352934302103640040673
>>>
>>> 77043115818403261176612826177818672838794518722182177510518702831
>>>
>>> 61634492654722608941290260942255029432493581352934302103640072617
>>>
>>> 77043115818403261176612826177818672838794518722182177510518662901
>>>
>>> 61634492654722608941290260942255029432493581352934302103640098081
>>>
>>> 77043115818403261176612826177818672838794518722182177510518631071
>>>
>>> 61634492654722608941290260942255029432493581352934302103640107537
>>>
>>> 77043115818403261176612826177818672838794518722182177510518619251
>>>
>>> 61634492654722608941290260942255029432493581352934302103640125441
>>>
>>> 77043115818403261176612826177818672838794518722182177510518596871
>>>
>>> 61634492654722608941290260942255029432493581352934302103640126809
>>>
>>> 77043115818403261176612826177818672838794518722182177510518595161
>>>
>>> 61634492654722608941290260942255029432493581352934302103640138113
>>>
>>> 77043115818403261176612826177818672838794518722182177510518581031
>>>
>>> 61634492654722608941290260942255029432493581352934302103640145529
>>>
>>> 77043115818403261176612826177818672838794518722182177510518571761
>>>
>>> 61634492654722608941290260942255029432493581352934302103640188633
>>>
>>> 77043115818403261176612826177818672838794518722182177510518517881
>>>
>>> 61634492654722608941290260942255029432493581352934302103640206489
>>>
>>> 77043115818403261176612826177818672838794518722182177510518495561
>>>
>>> 61634492654722608941290260942255029432493581352934302103640406169
>>>
>>> 77043115818403261176612826177818672838794518722182177510518245961
>>>
>>> 61634492654722608941290260942255029432493581352934302103640517337
>>>
>>> 77043115818403261176612826177818672838794518722182177510518107001
>>>
>>> 61634492654722608941290260942255029432493581352934302103640570497
>>>
>>> 77043115818403261176612826177818672838794518722182177510518040551
>>>
>>> 61634492654722608941290260942255029432493581352934302103640597761
>>>
>>> 77043115818403261176612826177818672838794518722182177510518006471
>>>
>>> 61634492654722608941290260942255029432493581352934302103640744377
>>>
>>> 77043115818403261176612826177818672838794518722182177510517823201
>>>
>>> 61634492654722608941290260942255029432493581352934302103640819017
>>>
>>> 77043115818403261176612826177818672838794518722182177510517729901
>>>
>>> 61634492654722608941290260942255029432493581352934302103640827753
>>>
>>> 77043115818403261176612826177818672838794518722182177510517718981
>>>
>>> 61634492654722608941290260942255029432493581352934302103640835361
>>>
>>> 77043115818403261176612826177818672838794518722182177510517709471
>>>
>>> 61634492654722608941290260942255029432493581352934302103640911513
>>>
>>> 77043115818403261176612826177818672838794518722182177510517614281
>>>
>>> 61634492654722608941290260942255029432493581352934302103640950273
>>>
>>> 77043115818403261176612826177818672838794518722182177510517565831
>>>
>>> 61634492654722608941290260942255029432493581352934302103641079297
>>>
>>> 77043115818403261176612826177818672838794518722182177510517404551
>>>
>>> 61634492654722608941290260942255029432493581352934302103641119281
>>>
>>> 77043115818403261176612826177818672838794518722182177510517354571
>>>
>>> 61634492654722608941290260942255029432493581352934302103641141169
>>>
>>> 77043115818403261176612826177818672838794518722182177510517327211
>>>
>>> 61634492654722608941290260942255029432493581352934302103641179329
>>>
>>> 77043115818403261176612826177818672838794518722182177510517279511
>>>
>>> 61634492654722608941290260942255029432493581352934302103641238537
>>>
>>> 77043115818403261176612826177818672838794518722182177510517205501
>>>
>>> 61634492654722608941290260942255029432493581352934302103641273553
>>>
>>> 77043115818403261176612826177818672838794518722182177510517161731
>>>
>>> 61634492654722608941290260942255029432493581352934302103641363337
>>>
>>> 77043115818403261176612826177818672838794518722182177510517049501
>>>
>>> 61634492654722608941290260942255029432493581352934302103641380089
>>>
>>> 77043115818403261176612826177818672838794518722182177510517028561
>>>
>>> 61634492654722608941290260942255029432493581352934302103641408961
>>>
>>> 77043115818403261176612826177818672838794518722182177510516992471
>>>
>>> 61634492654722608941290260942255029432493581352934302103641444913
>>>
>>> 77043115818403261176612826177818672838794518722182177510516947531
>>>
>>>
>>>
>>> I will try ratio (1/10) +1 next
>>>
>>> Dan
>>>
>>> --------------------------------------------------------------
>>>
>>>
>>>
>>>
>>>
>>> Perhaps due to an incomplete newsfeed, I have missed how _exactly_ these
>>>
>>> prime pairs that:
>>>
>>>
>>>
>>> (a) are in the ratio 1.25:1, and
>>>
>>>
>>>
>>> (b) have a product "very close" (defined explicitly) to the stated 130
>>> digit
>>>
>>> composite
>>>
>>>
>>>
>>> are generated.
>>>
>>>
>>>
>>> Please answer these 3 questions (the reason for asking them is given at
>>> the
>>>
>>> end):
>>>
>>>
>>>
>>> 1. Is it just a sieve routine that finds them?

>>
>> When building the smallest divisor that takes place first in the process
>> which in effect is building a polynomial. In one of my post you saw the
>> different stages in building this polynomial divisor.
>> The prime search happens "AFTER" this process is completed and the
>> smallest
>> divisor is established as the start for the search. I believe that when
>> you
>> start this prime search against a composite with unknown factors it will
>> sieve out a large sequential prime block for each unique ratio that can
>> never
>> be factors of the target composite.
>>
>> I could be 100% wrong on this belief, but if I am right it could aid in
>> 'NOT' factoring many sequential prime blocks created from many ratios.
>> These blocks of sequential primes are huge and with a special algorithm
>> that
>> bypasses these blocks in the factoring process should improve the search
>> of
>> the actual prime pair. Assuming, of course, the target composite is a
>> semi-prime
>>
>> So to answer your question #1, it is a polynomial sieve routine that I
>> believe
>> rules out any possible prime pairs as factors for any large blocks of
>> sequential
>> primes.
>> If you increment by just (2) of the first smallest prime in my prime pair
>> list of 1.25 ratio and at each increment divide it into the target
>> composite
>> you will observe a remainder pattern that is always the same.
>> Even doing it with the largest prime also shows it's own pattern.
>>

>>> 2. Is there any "gap" between "consecutive" prime pairs, where another
>>>
>>> pair of primes, which meet conditions (a) and (b) but which is not
>>>
>>> listed above, exists?

>>
>> I would say no because going back to my explanation above.
>>
>>

>>> 3. If so, what is special about the pairs chosen?
>>
>> Not so, I believe.
>>

>>>
>>>
>>> I ask because when I extract the product of, say, the last pair, I get:
>>>
>>>
>>>
>>> 47485133560063190433548259679204355907477810307482663990525310023918\
>>>
>>> 21388435849831808696656879013375857086348630738057687047859803
>>>
>>>
>>>
>>> which, of course, is very close to:
>>>
>>>
>>>
>>> 47485133560063190433548259679204355907477810307482663990525310023918\
>>>
>>> 21388435849831808696657092215642611599144927466443608010614619
>>>
>>>
>>>
>>> the original 130 digit composite.
>>>
>>> (Difference: 213202266754512796296728385920962754816)
>>>
>>>
>>>
>>> When I then try to refactorise this product, written out explicitly of
>>>
>>> course, Dario Alpern's applet does it in just a couple of seconds on my
>>>
>>> computer.

>>
>> That large composite (1699 digits) which created the prime pair I posted
>> took quite a while to confirm as primes for each prime.
>> No complaints mind you, because they are big integers.
>>

>>> This is the case for all the pairs I checked.
>>
>> Python does good on their probable prime routine.
>>
>>

>>> But the original 130 digit number is not at all so trivial to
>>> decompose....
>>>
>>>
>>>
>>> Hence questions 1-3 above.

>>
>> Possibly I can run a much smaller toy composite that has two equal length
>> factors and perform my ratio stunt employing many ratios and thus many
>> smaller divisor that remove all these blocks of sequential primes as
>> candidates. Just a thought on possibly proving my point!
>>
>> Hope I answered the three questions to your satisfaction?
>> Please respond if not.

>
>
> Thank you.
>
> The fact remains that "your" composites, if entered into the Alpertron
> applet (after their consitutent prime pair has been multiplied out, so
> what I enter into the applet does _not_ have a "*" in it) are very easy
> to factorise, while the original composite chosen by David Bernier is not.
>
> Try it for yourself, please. In this order!
>
> Choose one of your pairs yourself.
>
> Multiply them out using something other than the Alpertron applet.
>
> Put the product into http://www.alpertron.com.ar/ECM.HTM and, having
> switched
> the number of threads to the maximum for your CPU(s), factorise it.
>
> Depending on the power of your PC, it will do it taking from under 1 second
> to about 15 seconds.
>
> Now take the 130 digit composite supplied by David. Use the applet to
> factorise
> it.
>
> Go and make some coffee.
>
> Have a walk.
>
> Do some gardening.
>
> Then even bake a cake? If your PC is old, you will have time.
>
> I think you will then see my point.
>
> If they appear to be of a different type from the POV of the applet, then
> they _are_ of a different type.
>
> It follows that either there is something unusual about your prime pairs, or
> about David's composite.


I have a large collection of pseudo-random bytes, going back
to a video capture (on a few occasions) of "snow" or
"white noise" on a CRT tube. I mixed the bytes using recommended
procedures/heuristics. A 130 digits modulus was chosen,
as I had previously factored RSA-129 about two years
ago with CADO-NFS 1.0 .

Following Pubkeybreaker's ECM and quadratic sieve threat
discussion, I decided on two 65-digit primes.
I extracted digits from a base64 encoding of "random bytes"
by hand, and finally obtained two large enough 65-digit
pseudo-random numbers m1 and m2
(meaning that the product was 130 digits).

Using PARI/gp, I tested for primality the next few thousand
odd numbers after the pseudo-random 'm1' and 'm2'.

This gave the primes p > m1 , and q > m2, with
p*q having 130 digits.

So, p and q are "nothing-up-my-sleeve" 65-digit primes.
I guess they were selected through partly noise-dependent
procedures, anyway I didn't interfere to cause bias.

There are, from what I recall,
weak rsa moduli (unrelated to NSA work on promoting
"fake" rng generators). I didn't test for
"weak rsa moduli" in the original, pre-NSA-revelations,
sense.

dave

--
http://www.bibliotecapleyades.net/sociopolitica/last_circle/1.htm


Date Subject Author
1/18/14
Read Re: Help with a factorisation, Please [Important]
Daniel Joyce
1/18/14
Read Re: Help with a factorisation, Please [Important]
Port563
1/18/14
Read Re: Help with a factorisation, Please [Important]
Daniel Joyce
1/18/14
Read Re: Help with a factorisation, Please [Important]
Daniel Joyce
1/18/14
Read Re: Help with a factorisation, Please [Important]
Port563
1/18/14
Read Re: Help with a factorisation, Please [Important]
David Bernier
1/18/14
Read Re: Help with a factorisation, Please [Important]
Daniel Joyce
1/18/14
Read Re: Help with a factorisation, Please [Important]
Port563
1/18/14
Read Re: Help with a factorisation, Please [Important]
Daniel Joyce
1/18/14
Read Re: Help with a factorisation, Please [Important]
Port563
1/18/14
Read Re: Help with a factorisation, Please [Important]
Port563
1/18/14
Read Re: Help with a factorisation, Please [Important]
Daniel Joyce
1/18/14
Read Re: Help with a factorisation, Please [Important]
Daniel Joyce
1/19/14
Read Re: Help with a factorisation, Please [Important]
Daniel Joyce
1/19/14
Read Re: Help with a factorisation, Please [Important]
Port563
1/19/14
Read Re: Help with a factorisation, Please [Important]
Daniel Joyce
1/24/14
Read Re: Help with a factorisation, Please [Important]
David Bernier
1/24/14
Read Re: Help with a factorisation, Please [Important]
Daniel Joyce
1/24/14
Read Re: Help with a factorisation, Please [Important]
Port563
1/24/14
Read Re: Help with a factorisation, Please [Important]
David Bernier
1/25/14
Read Re: Help with a factorisation, Please [Important]
Port563
1/25/14
Read Re: Help with a factorisation, Please [Important]
Port563
1/25/14
Read Re: Help with a factorisation, Please [Important]
Daniel Joyce
1/25/14
Read Re: Help with a factorisation, Please [Important]
Port563
1/25/14
Read Re: Help with a factorisation, Please [Important]
Daniel Joyce
1/25/14
Read Re: Help with a factorisation, Please [Important]
Port563
1/26/14
Read Re: Help with a factorisation, Please [Important]
Daniel Joyce

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.