Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Help with a factorisation, Please [Important]
Posted:
Jan 18, 2014 2:55 PM


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 UTC5, 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 >> semiprime >> >> 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 13 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 pseudorandom 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 RSA129 about two years ago with CADONFS 1.0 .
Following Pubkeybreaker's ECM and quadratic sieve threat discussion, I decided on two 65digit primes. I extracted digits from a base64 encoding of "random bytes" by hand, and finally obtained two large enough 65digit pseudorandom 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 pseudorandom 'm1' and 'm2'.
This gave the primes p > m1 , and q > m2, with p*q having 130 digits.
So, p and q are "nothingupmysleeve" 65digit primes. I guess they were selected through partly noisedependent 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, preNSArevelations, sense.
dave
 http://www.bibliotecapleyades.net/sociopolitica/last_circle/1.htm



