Hi all, Dana Jacobsen recently advised us that certain composites were being passed as prime by flint's primality testing functions n_is_prime and n_is_probabprime. This in turn affects n_is_factor which did not provide a factorisation of these numbers.
This bug has been fixed in flint-2.4.4, and we strongly recommend users update to this latest version of flint. What precisely is the bug? For inputs in the range [1122004669633, 10000000000000000 = 10^16), the functions n_is_prime and n_is_probabprime occasionally passed composites as prime, e.g. 2007193456621 = 1001797 x 2003593 2744715551581 = 1171477 x 2342953 were declared prime. Because of the size of the numbers involved, the bug only affects 64 bit machines. What we believe to be a complete list of composites passed as prime by flint is reproduced below. The probability of hitting one of these values at random should be around 1 in 10^12, i.e. far lower than the probability that the code was miscompiled or perhaps even that there was a hardware bug! Which versions of flint are affected? All versions from flint 1.1.0 -- 2.4.3 (inclusive) are affected. Does this affect Sage? Sadly, yes. sage: factor(2007193456621) 2007193456621 Does this affect multimodular algorithms in flint? Probably not. For efficiency reasons, flint usually uses primes that are FLINT_BITS bits long, none of which are in the critical range. How did the bug occur? In 2008, the following page: http://primes.utm.edu/prove/prove2_3.html gave a reference to a result which stated that any natural number n in the range n < 10^16 except n = 46856248255981 was prime if it was simultaneously a strong probable prime to bases 2, 3, 7, 61 and 24251: https://web.archive.org/web/20081013050700/http://primes.utm.edu/prove/prove2_3.html This result is false. The result was based on, and a misinterpretation of a (correct) result of Charles Greathouse (this is not an issue of using an internet table of values -- the published work on this by Jaeschke contains an error corrected online by Greathouse). Although Greathouse clarified his work publicly since 2006 and the webpage in question referring to his work was amended in Dec 2008, numerous people used the incorrect values for some time, apparently unaware of the changes. We ourselves have only recently become aware of this due to Dana Jacobsen exhaustively testing the flint primality code up to 2^64 against Feitma's tables of base-2 pseudoprimes. This independently verifies flint's primality testing, contingent only on the (huge) databases of 2-psp's published online by Feitsma and Galway (amounting to a huge number of CPU years of effort by). This is one of the three most serious bugs in flint, and possibly the most embarrassing. A lot of diligence has since gone into correcting and checking the implementation in flint-2.4.4. Acknowledgements Thanks very much to Dana Jacobsen for spotting this bug and providing a patch to fix it! Full list of composites passed as prime by flint's n_is_prime(): WARNING: this list is flint specific. It is **NOT** a complete list of composites passed as prime by a test using the Greathouse bases! 2007193456621 2744715551581 9542968210729 17699592963781 19671510288601 24983920772821 24984938689453 29661584268781 37473222618541 47922612926653 48103703944453 49110566041153 49752242681221 91206655032481 91481980096033 119034193492321 123645258399601 128928036060253 137364148720147 150753857310253 153131886327421 155216912613121 185610214763821 224334357392701 227752294950181 230058334559041 304562854940401 306001576998253 335788261073821 377133492079081 379242177424951 389970770948461 397319638319521 448114903362253 523235160050221 628999496281621 699349238838253 746667678235753 790198268451301 794036495175661 823820871230281 867739535711821 1039918661294761 1099127938585141 1104388025338153 1173374598605653 1262797719066157 1265872947674653 1325898212229667 1327034517143653 1418575746675583 1666122072463621 1837400535259453 1857422490084961 1870756820971741 1914550540480717 2018963273468221 2163829000939453 2206020317369221 2301037384029121 2416062055125421 2435076500074921 2545656135020833 2594428516569781 2669983768115821 2690937050990653 2758640869506607 2833525461416653 2876662942007221 2932155806957821 2957010595723801 3183606449929153 3220133449185901 3424103775720253 3625360152399541 3939300299037421 3947917710714841 3980273496750253 4182256679324041 4450605887818261 4727893739521501 4750350311306953 4755334362931153 5756440863559753 5760976603475341 5794399356078761 5954850603819253 6125544931991761 6320931714094861 6347593619672581 6406268028524101 6510632945054941 6620082224794741 6627325072566061 6844056606431101 6989404981060153 7144293947609521 7288348593229021 7288539837129253 7406102904971689 7430233301822341 7576425305871193 7601696719033861 7803926845356487 7892007967006633 7947797946559453 8207000460596953 8295064717807513 8337196000698841 8352714234009421 8389755717406381 8509654470665701 8757647355282841 8903933671696381 8996133652295653 9074421465661261 9157536631454221 9188353522314541 -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
