jimh@hpsadla.HP (Jim Horn) (11/15/86)
A request for factorization...
After the remarkable factorization done earlier and displayed in this
notestring, I'd like to pass on a request from a friend in Kansas.
The "Canadian Farm & Home Almanac" of 1984 (Vol 19) has a set of "Argument
Clinchers" (pg 96) which includes the following:
The possibility of two persons having identical fingerprints is one
chance in 1,606,937,974,174,171,729,761,809,705,564,167,968,221,
676,069,604,401,795,301,376. That first digit is novemdecillion.
Efforts to locate the derivation of this value have been fruitless. The
editors of the book claim to have gotten the number from Scotland Yard, but
requests from that source have turned up nothing. An analysis of the
number was then attempted to try to discover its derivation.
At this point, we know that:
1606937974174171729761809705564167968221676069604401795301376 =
2 ^ 43 *
17 *
4937 *
5434669 *
400519950023277930387559326324618247 (approx. 4E35)
This last value is composite, but has no factors less than 5000000000 (5E9).
At this point, further attempts at factorization using uMath have yielded
nothing. Neither of us has had a chance to impliment the more advanced
factorization algorithms given by Knuth (The Art of Computer Programming,
Vol. 2) to break it, although we hope to. Meanwhile, would anyone else
care to try?
I know this is a serious notes string, and apologize for what may appear a
relatively trivial request. But we would like to find the two (no more or
less) factors of that last value (4.005..E35), and would greatly appreciate
it if someone with the capabilities to do so would let us know what they
are.
You can reach the source of this quandary (no e-mail - sorry!) at:
Robert G. Wilson, Jr.
408 Century Plaza Building
Wichita, KS 67202
Work: (316) 265-7957 Home: (316) 682-5678
Or you can e-mail to me and I'll be happy to pass it along. Many thanks!!!
Jim Horn {The World}!hplabs!hpfcla!hpsadla!jimh}
Work: (707) 794-3130 Home: (707) 523-4890bs@linus.UUCP (Robert D. Silverman) (11/16/86)
> 1606937974174171729761809705564167968221676069604401795301376 = > 2 ^ 43 * > 17 * > 4937 * > 5434669 * > 400519950023277930387559326324618247 (approx. 4E35) > > This last value is composite, but has no factors less than 5000000000 (5E9). > At this point, further attempts at factorization using uMath have yielded > nothing. Neither of us has had a chance to impliment the more advanced > factorization algorithms given by Knuth (The Art of Computer Programming, > Vol. 2) to break it, although we hope to. Meanwhile, would anyone else > care to try? > > I know this is a serious notes string, and apologize for what may appear a > relatively trivial request. But we would like to find the two (no more or > less) factors of that last value (4.005..E35), and would greatly appreciate > it if someone with the capabilities to do so would let us know what they > are. > > You can reach the source of this quandary (no e-mail - sorry!) at: > > Robert G. Wilson, Jr. > 408 Century Plaza Building Here's the factorization: It took about 40 sec on my SUN/3-75. The algorithms in Knuth are obsolete. 4628238223878839 86538317746230817073 Bob Silverman
lambert@mcvax.uucp (Lambert Meertens) (11/16/86)
In article <2380002@hpsadla.HP> jimh@hpsadla.HP (Jim Horn) quotes from the "Canadian Farm & Home Almanac" the following "Argument Clincher": > The possibility of two persons having identical fingerprints is one chance in > > 1606937974174171729761809705564167968221676069604401795301376. The number quoted is suspiciously close to 2^200 = 1606938044258990275541962092341162602522202993782792835301376. That would correspond to twenty yes/no fingerprint characteristics for each finger. The question remains where the middle segment of digits comes from. One guess is that someone determined the leading digits using a six-place log table, the final digits using modular arithmetic, and proceeded to fill in the rest at random, thinking no-one would bother to check it out. Another possibility is that the (human) computer really goofed in doing the arithmetic. I tried to reconstruct a scenario in which the number is obtained by repeated doubling in decimal arithmetic while being subjected to a few random errors in the digits. The simplest I could find (but I did not try that hard) is given below. A "v" stands for an assumed error. I have no idea if the number of v's is significantly lower than needed to explain an arbitrary random middle segment. 22300745198530623141535718272648361505980416 = 2^144 vvvvvv v 22300745198530624250645715272648361505980416 -------------------------------------------- * 2^3 178405961588244994005165722181186892047843328 vvv 178405961588244994005165722270186892047843328 --------------------------------------------- * 2^4 2854495385411919904082651556322990272765493248 vvv 2854495385411919904082651556323700272765493248 ---------------------------------------------- * 2^2 11417981541647679616330606225294801091061972992 v 11417981541647679616330606225294802091061972992 ----------------------------------------------- * 2^1 22835963083295359232661212450589604182123945984 v 22835963083295359232661212450589604282123945984 ----------------------------------------------- * 2^2 91343852333181436930644849802358417128495783936 v 91343852333181436930644849802358417158495783936 ----------------------------------------------- * 2^1 182687704666362873861289699604716834316991567872 vvv 182687704666256873861289699604716834316991567872 ------------------------------------------------ * 2^2 730750818665027495445158798418867337267966271488 v 730750818665027495445158798418867337268966271488 ------------------------------------------------ * 2^1 1461501637330054990890317596837734674537932542976 vvv 1461501637330054990890317596837734674538002542976 ------------------------------------------------- * 2^4 23384026197280879854245081549403754792608040687616 v 23384026197280879854245081549403754792608030687616 -------------------------------------------------- * 2^13 191561942608124967765975708052715559261044987392950272 vv 191561942598124967765975708052715559261044987392950272 ------------------------------------------------------ * 2^23 1606938044174171889601405952376674162141676069604401795301376 vvv 1606937974174171889601405952376674162141676069604401795301376 -- Lambert Meertens, CWI, Amsterdam; lambert@mcvax.UUCP
gjfee@watmum.UUCP (Greg Fee) (11/16/86)
400519950023277930387559326324618247 = 4628238223878839 * 86538317746230817073; Jim Horn asked for the above factorization. It was found by using maple version 4.0 on a VAX-11/785 in just under 40,000 seconds. The "ifactor" command in maple had used the Morrison-Brillhart method to factor the number.