7 ms·

I don't work for the NSA—I just have a laptop, and a copy of Mathematica. The factorization took about 10 seconds. Mathematica is really a pretty remarkable pi

I don't work for the NSA—I just have a laptop, and a copy of Mathematica. The factorization took about 10 seconds. Mathematica is really a pretty remarkable piece of software. I doubt it's world class for factorization, but it gives you easy access to a lot of pretty darn good algorithms for a wide range of problems. There's 1 sentence on the implementation of FactorInteger in the docs, FWIW: http://reference.wolfram.com/language/tutorial/SomeNotesOnInternalImplementation.html#12915 http://reference.wolfram.com/language/tutorial/SomeNotesOnIn...

waynecochran 11y ago
Okay ... wow ... how big do the numbers need to get to bog down Mathematica?
- Pyxl101 11y ago
  The numbers that we're talking about are not big. The number you specified: 641071800653367850802176606120792275422168080497001121 OK, so take a 64 bit integer. That's the typical size of an integer in a modern programming language. A signed integer can represent 2^63-1 which is 9223372036854775807. Imagine a "big integer" which is a composite of multiple 64-bit integers. With a big integer made up of two regular integers, you can represent the value 170141183460469231731687303715884105727. With three, you get to 3138550867693340381917894711603833208051177722232017256447 if I'm doing the math right. That's already in the ballpark of the number you mentioned - just three regular integers together. Granted, I'm not talking about how difficult the factoring is, but it's worth noting that the size of the numbers are pretty small to a computer. Modern computers are really fast and can brute force a large number of computations. Mathematica probably has a fairly optimized general purpose factoring algorithm as well. A number like this might be more difficult to factor: 16158503035655503650357438344334975980222051334857 74201606517271376232756943394544659860070576145673 18443589804609490097470597795752454605475440761932 24141560315438683650498045875098875194826053398028 81919203378413839610932130987808091904716923808523 52908229260181525214437879457705329043037761995619 65192760957166694834171210342487393282284747428088 01766316102903890282966551309635423015707512929643 20885583629718018592309286787991755761508229522018 48806616643615613562842355410104862578550863465661 73483927129032834896752299863417649931910776258319 47186677718010677166148023226592393024760740967779 26805529798115327
archgoon 11y ago
pari-gp is freely available for linux, and it's source is available if you're interested in their implementation. http://pari.math.u-bordeaux.fr/ http://pari.math.u-bordeaux.fr/ The relevant file is src/basemath/ifactor1.c

waynecochran 11y ago

Okay ... wow ... how big do the numbers need to get to bog down Mathematica?

Pyxl101 11y ago
The numbers that we're talking about are not big. The number you specified: 641071800653367850802176606120792275422168080497001121 OK, so take a 64 bit integer. That's the typical size of an integer in a modern programming language. A signed integer can represent 2^63-1 which is 9223372036854775807. Imagine a "big integer" which is a composite of multiple 64-bit integers. With a big integer made up of two regular integers, you can represent the value 170141183460469231731687303715884105727. With three, you get to 3138550867693340381917894711603833208051177722232017256447 if I'm doing the math right. That's already in the ballpark of the number you mentioned - just three regular integers together. Granted, I'm not talking about how difficult the factoring is, but it's worth noting that the size of the numbers are pretty small to a computer. Modern computers are really fast and can brute force a large number of computations. Mathematica probably has a fairly optimized general purpose factoring algorithm as well. A number like this might be more difficult to factor: 16158503035655503650357438344334975980222051334857 74201606517271376232756943394544659860070576145673 18443589804609490097470597795752454605475440761932 24141560315438683650498045875098875194826053398028 81919203378413839610932130987808091904716923808523 52908229260181525214437879457705329043037761995619 65192760957166694834171210342487393282284747428088 01766316102903890282966551309635423015707512929643 20885583629718018592309286787991755761508229522018 48806616643615613562842355410104862578550863465661 73483927129032834896752299863417649931910776258319 47186677718010677166148023226592393024760740967779 26805529798115327

archgoon 11y ago

pari-gp is freely available for linux, and it's source is available if you're interested in their implementation. http://pari.math.u-bordeaux.fr/ http://pari.math.u-bordeaux.fr/ The relevant file is src/basemath/ifactor1.c