January 2012 - mathfun@mailman.xmission.com

Re: [math-fun] Warren D Smith video lecture: How I broke AES -- if I did it
by Henry Baker 19 Jan '12

19 Jan '12

Warren: I really enjoyed the video, even though in high def the slides & the board are often unreadable. Your Matsui/Smith attack is really cool & is worth teaching -- whether or not it works in practise -- because it brings together a number of important concepts in coding theory in a cool way. If you still have the slides & want to link to the video on your own web site, it might be nice to make the slides available for better reading. At 04:47 PM 1/18/2012, Warren Smith wrote: >hmm. Did not realize I'd been videod+internetted. Hope it came out well. >The paper that lecture was based on, can be read here: > >http://rangevoting.org/WarrenSmithPages/homepage/works.html > >paper#100 > >and it described what I called an alleged "nonconstructive break" of >the AES cryptosystem. > >Later an alleged "genuine break" of AES was produced: > >http://research.microsoft.com/en-us/projects/cryptanalysis/aesbc.pdf > >but both theirs and mine have no real practical impact. > >My paper however also cited a "(cheating) break" of AES by Daniel J. >Bernstein which I think is very serious practically speaking.

1 0

[math-fun] Strong pseudoprimes [Jaeschke, Gilchrist, Feitsma]
by Warren Smith 18 Jan '12

18 Jan '12

>Just a curiosity, but two of the six exceptions below fit into the (q-1)=k(p-1) test, albeit with composite p. 151*751*28351 = 28351 * 113401 151*2551*192601 = 192601 * 385201 (hard #1) --Rich --actually, even more: 331*2971*49171 = 49171*983401, note 983400/49170=20 (hard #2) where note the only 2 "hard" ones among Jaeschke's 6 exceptions are covered by the (q-1)=k*(p-1) test if k=20 is also considered. --Warren D. Smith

1 0

Re: [math-fun] math-fun Digest, Vol 107, Issue 23
by Warren Smith 18 Jan '12

18 Jan '12

> The Adams-Shanks test involves these two 3x3 matrices A= > [ r -s 1 ] > [ 1 0 0 ] > [ 0 1 0 ] > and Ainverse= > [0 1 0] > [0 0 1] > [1 -r s]. > They study > (r,s) = (0,-1) Perrin > (r,s) = (1,0) "Secundo" > (r,s) = 1,-1) > (r,s) = -1,-2). > From: Robert Baillie <rjbaillie(a)frii.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: Re: [math-fun] Matrix-Product Primality Tests > Message-ID: <4F172BCF.7050804(a)frii.com> > Content-Type: text/plain; charset=ISO-8859-1; format=flowed > > interesting synopsis! > > actually, the statistical independence has been pointed out before, in the > "lucas pseudoprimes" paper by baillie and wagstaff. in fact, it seems to be > "better" than mere independence: the two types of pseudoprimes appear to avoid > each other. > > you might also find this interesting: "TWO CONTRADICTORY CONJECTURES CONCERNING > CARMICHAEL NUMBERS" by granville and pomerance. > also, "on the distribution of pseudoprimes" by pomerance. > > basically, there are heuristic arguments for the number of carmichaels psp's,, > etc., up to x being > x^.99 (for ridiculously large x). > > it seems unlikely that O(1) psp tests would suffice; the number of tests you do > should increase (slowly?) as N increases. however, it also seems that only a > small number of tests gives pretty good results. --The Perrin/Adams-Shanks test based on a 3x3 matrix, really was not doing the right thing from the point of view of getting "independence" or "avoidance" versus earlier tests based on 2x2 and 1x1 matrices. Really, the idea of a pseudoprime test based on a kXk matrix or degree=k polynomial, ought to be to devise the matrix so that exponentiating it to the power N^k-1 (mod something) should deliver 1 if N is a prime because N^k-1 is the order of the cyclic multiplicative group of nonzeros inside the Galois field with N^k elements. In the case k=2, we note N^2-1=(N+1)*(N-1) so we -- if we want to be intelligent -- should contrive things to use the power N+1 and not N-1 which was already covered by scalar tests. Which is exactly what the "true Lucas" tests already do. In the case k=3, note N^3-1 = (N-1)*(N^2+N+1) and Adams+Shanks foolishly (in our view) concentrated on N-1 which was already covered by scalar tests, but really to go for independence/avoidance should have gone for the exponent N^2+N+1. One could continue on to degree k=4. Then N^4-1 = (N^2+1)*(N-1)*(N+1) and we should to be intelligent focus on the exponent N^2+1. It seems plausibly hopeful that by going order by order in this way cooking up a test at each order based on an exponent that in general has GCD<=2 with any preceding exponent, we can keep attaining "independence" or "avoidance" at each level, thus getting an extremely strong combined pseudoprime test. Then based on the Erdos x^0.99 type conjectures combined with independence/avoidance conjectures, going up to k of order lnlnN ought to suffice. The Pomerance/Granville "Two contradictory conjectures" paper Baillie suggested discusses the "x^0.99 Erdos" versus "x^0.5 or less Computer-based" count conjectures for Carmichael numbers below x. They believe in Erdos, but doubt it ever gets above x^0.5 until x>10^100. Their conjectural inequality (2) and their conjecture 1 would basically imply that the $620 combination Miller+Lucas test should have only a small finite set of N that fail it... up until the point where Erdos's reasoning starts to become meaningful, which is probably over-100-digit-long N.

1 0

[math-fun] Strong pseudoprimes [Jaeschke, Gilchrist, Feitsma]
by Warren Smith 18 Jan '12

18 Jan '12

Gerhard Jaeschke tabulated all 101 composites N<10^12 that pass the Miller pseudoprime tests with A=2, 3 and 5. Of these 101, Jaeschke found 95 had the form N=p*q with p,q odd primes with (q-1) = k*(p-1) for k in the set {2,3,4,5,6,7,13, 4/3, 5/2}. Thus, combining (i) the Miller tests with A=2,3,5 with (ii) trying integers very near sqrt(N/k) as possible divisors of N with (iii) a lookup table for the remaining 6 exceptions yields a prime test valid for N<10^12. Gerhard Jaeschke: On strong pseudoprimes to several bases, Maths. of Comput. 61,204 (1993) 915-926. http://cr.yp.to/bib/1993/jaeschke.pdf Jaeschke also claims that there are no strong pseudoprimes below 10^12, common to the four prime bases A=2, 13, 23, and 1662803. Further, if we examine the 6 exceptional N below 10^12, which are 151*751*28351 note 750/150=5, 28350/150=189=7*3*3*3 ** 397*4357*8317 note 4356/396=11, 8316/396=21=3*7 ** 331*2971*49171 note 2970/330=9, 49170/330=149 151*2551*192601 note 2550/150=17, 192600/150=1284=2*2*3*107 1171*10531*19891 note 10530/1170=9, 19890/1170=17 ** 1231*6151*11071 note 6150/1230=5, 11070/1230=9=3*3 ** we see that four out of these six N (those with **) would have been spotted if we had tried integers very near cbrt(N/m) as potential factors of N for the m with 45<=m<=945 got by multiplying {3,5,7,11,17} in various combinations with at most 4 prime factors (counting repeated factors repeatedly) in all and with at most one factor>7 allowed in the mix. http://oeis.org/A006945 also is relevant to this. --- Jeff Gilchrist has a web page on this: http://gilchrist.ca/jeff/factoring/pseudoprimes.html and he finds using Jan Feitsma's 2-pseudoprime database http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html that the $620 prize problem (of finding a composite N which is both Miller pseudoprime with A=2 and also Lucas pseudoprime according to the Baillie-PSW test) has no solution below 2^64. This particular Lucas test employs P=1 and Q=(1-D)/4 where D is the first member of {5, -7, 9, -11, 13, -15, ...} for which GCD(D,N)=1 and JacobiSymbol(D|N) = -1.

2 1

[math-fun] Warren D Smith video lecture: How I broke AES -- if I did it
by Henry Baker 18 Jan '12

18 Jan '12

FYI -- http://149.157.192.253/seminars/Flyer_Smith.pdf How I broke AES (Advanced Encryption Standard) Â if I did it Sunday, February 01, 2009 4:00 PM Speaker: Dr. W. D. Smith Abstract: We describe a new simple but more powerful form of linear cryptanalysis. It appears to break AES (and undoubtedly other cryptosystems too, e.g. SKIPJACK). *But the break is "nonconstructive". *Even if this break is broken (due to the underlying models inadequately approximating the real world) we explain how AES still could contain "trapdoors" which would make cryptanalysis unexpectedly easy for anybody who knew the trapdoor. We then discuss how to use the theory of BLECCs to build cryptosystems provably *not containing trapdoors of this sort, *secure against our strengthened form of linear cryptanalysis, *secure against "differential" cryptanalysis, *secure against D.J. Bernstein's timing attack. Using this technique we prove a fundamental theorem: it is possible to thus encrypt N bits with security 2^(cN), via an circuit Q_N containing <= cN two-input logic gates and operating in <= c log(N) gate-delays, where Q_N is constructible in polynomial (in N) time. Download video in hi def (370 Mbytes): http://149.157.192.253/seminars/videos/06-w_smith_hi.mp4 Watch video online: http://149.157.192.253/seminars/videos/show_video.php?file=06-w_smith

1 0

[math-fun] Matrix-Product Primality Tests
by Warren Smith 18 Jan '12

18 Jan '12

Let N>10 be an odd integer we wish to test for primality. Let N = v * 2^s + 1 where s>0 and v>0 are integers. 0. Trial division by 2,3,5,7,11,... is useful as a quick screen to spot easy composites, but ultimately is extremely inefficient. 1. The following primality test is well known: Miller-Rabin et al "strong A-pseudoprime test": Let A be a constant with 0<A<N and GCD(A,N)=1. [If GCD>1 then we have found a factor of N and can quit now.] Compute J=A^v mod N. If |J|=1 then output "N probably prime" and stop. Now square J (mod N) repeatedly up to s-1 times; if ever J=-1 then output "N probably prime" and stop. Finally, output "N is definitely composite." This test is known to fail (i.e. say "probably prime" when in fact N is composite) for less than 1/4 of the A's chosen randomly mod N with GCD(A,N)=1, but for most N fails much less often, e.g. Pomerance, Selfridge, Wagstaff found that there were only 13 cases (which they tabulated) among the 2<N<25*10^9 that simultaneously failed the three tests with A=2,3, and 5, and all 13 happened to have the form N=(k+1)*(r*k+1) for r in the set {2, 3, 4, 5, 7} except for N=397*4357*8317 which has the form N=(k+1)*(208*k+1). These special forms could be detected (and hence N factored) by solving quadratic equations for k. The least N which simultaneously fails the 7 tests based on A=2,3,5,7,11,13,17 is N=(k+1)*(3*k+1) where k=10670053; this N is 3.4*10^14 approximately. This indicates these 7 tests could be crudely regarded as acting as though they were "independent with failure probability 1/119 each." Three tests using A=2, 7, and 61 suffice for all N<4759123141. 2. E.Lucas followed by R.Baillie & S.S.Wagstaff had an idea which I shall regard as similar to the above, but now the quantity A being exponentiated mod N is a 2x2 matrix, not a scalar. Specifically,let A be [ P 1 ] [ -Q 0 ] where P>0 and Q are integers chosen so that 0<=P,Q<N and D=P*P-4*Q is nonzero and GCD(N,Q)=1 and GCD(N,D)=1, and JacobiSymbol(D|N) = -1. Compute J=A^v mod N. If the top left entry of J is 0, then N is a "probable prime" and stop. Now for each k with 0<=k<s do{ if the first entry of (P,2)*J is 0, then{ output "N is a probable prime" and stop} square J. } If we reach here, "N is definitely composite." It is known that at most 4/15 of the possible random choices of P,Q can cause failure [F.Arnault: Math. Comput. 66,218 (1997) 869-881] unless N=(k-1)*(k+1) which could be detected by testing N+1 for squareness... (and even for these N failure probability<1/2) but for most N failures are much rarer. Usually Lucas failures are of the form N=(k-1)*(r*k+1) for r in the set {1,2,3,4,5} or of the form N=(k+1)*(r*k-1) for r in the set {2}, or N=(k+1)*(r*k-1) for r in the set {2,4,6,20}. Again, it is possible to detect and factor N of these specially likely to be bad forms, by solving quadratics for k. A simpler idea is simply finding sqrt(N/m) for m=1,2,3,... and if any of these result in values very close to integers, then test integers near these square roots as possible factors of N. Furthermore, although in the Miller-Rabin test failure for some A makes failure for other A much more likely, Miller-Rabin and Lucas failures tend to behave like statistically independent events; the reason for that, which apparently has not been pointed out before, is the pretty much disjoint natures of the bad-N sets discussed above. Pomerance, Selfridge & Wagstaff offerred $620 for anybody finding a composite N (congruent to +-2 mod 5) such that N is a Miller-Rabin pseudoprime with A=2 *AND* N is a Lucas pseudoprime with P=1, Q=-1 (or prove none exist). The prize is uncollected. Apparently Jeff Gilchrist has shown there are no such N below 10^17. The Miller-type primality test produces as a side effect, knowledge that certain numbers A are square or nonsquare mod N, This knowledge can be used to produce parameters for use in a Lucas-type test, thus saving time when doing combined tests. I have not seen that pointed out before either. 3. R.Perrin, followed by Wm.Adams & Daniel Shanks, suggested another test which can be viewed as based on exponentiating 3x3 matrices. Wm Adams & Daniel Shanks: Strong PrimalityTests That Are Not Sufficient, Maths of Comput 32 (1982) 255-300 GC Kurtz, D.Shanks, H.C.Williams: Fast Primality Tests for Numbers Less Than 5*10^10, Maths of Comput 46,174 (1986) 691-701 http://www.ams.org/journals/mcom/1986-46-174/S0025-5718-1986-0829639-7/S002… The Adams-Shanks test involves these two 3x3 matrices A= [ r -s 1 ] [ 1 0 0 ] [ 0 1 0 ] and Ainverse= [0 1 0] [0 0 1] [1 -r s]. They study (r,s) = (0,-1) Perrin (r,s) = (1,0) "Secundo" (r,s) = 1,-1) (r,s) = -1,-2). 4. Retrospective. All these matrix exponentials mod N, can also be viewed as polynomial(x) exponentials modulo both a fixed polynomial and mod N. This polynomial-based view of it is probably better, and it ultimately succeeded in yielding the rigorous AKS primality test. AKS involves polynomials of degree up to of order (logN)^2, or equivalently matrices of size up to order (logN)^2 x (logN)^2. Jon Grantham has given an excellent survey of this all that unifies everything using the polynomial view, he calls it "Frobenius pseudoprimes": http://www.pseudoprime.com/pseudo1.ps I suspect, however, that AKS is overkill. First of all, I suspect that O(logN) tests similar to Miller and Lucas suffice to get the failure rate so low than only a finite number of bad N exist (which could be listed in a finite size lookup table) -- because this in fact is true if random A are used in Miller's tests, and hence some fast deterministic choice of the A's as a function of N ought to work if there is any justice. If we were really smarter then perhaps we could show only O(1) tests suffice. My reason for the second suspicion is this. Suppose we could argue that the only N which fail some such test, need to be Carmichael numbers or anyhow something like them with at least 3 factors and with the factors having a specific form, OR if there are 2-factor baddies, see below. It is fairly clear from computer output there are about N^(1/3+o(1)) Carmichael numbers up to N although the rigorous count bounds on them are considerably weaker. I.e. the "probability density" of bad N would be about N^(o(1)-2/3) for those kind of N. Then if we had two tests which were *independent* the density of *doubly* bad N would be about N^(o(1)-4/3), which is fast enough falloff to get only a finite set of bad N in all. Further if the 2-factor baddies by means of quadratic-solving for specific common forms could be made rare enough to have density below N^(-1/2) * (logN)^(-K) for some constant K>0.5, then the doubly-bad N would have density below N^(-1) * (logN)^(-2*K) which would be low enough to assure only a finite set of doubly-bad N existed. But on the other hand... Erdos has conjectured that eventually, the number of Carmichaels below N will exceed N^0.99. It has never been observed to exceed N^0.4 so far, but Erdos says to hell with the computer evidence since his ideas only kick in for N with huge numbers of prime factors. Anyhow, if Erdos is correct, then my above flaky density arguments are destroyed. More precisely, Erdos conjectured the number of Carmichaels and pseudoprimes below N ultimately behaves like N^(1 - constant*lnlnlnN / lnlnN) and upper bounds of this kind have been proven. If Erdos is right then even if all the Miller-esque and Lucas-esque and etc test failures acted "independent" then the best we could hope to hope for would be that about lnlnN / lnlnlnN tests would be needed. That's bigger than O(1), but a lot smaller than O(logN). -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

Re: [math-fun] continued fraction to represent P as x^2+K*y^2 for K=1, 2, 3, 4, 7
by N. J. A. Sloane 17 Jan '12

17 Jan '12

Warren, you know there is a (wonderful) book on this subject: D A Cox, Primes of the form x^2+ny^2, Wiley 1989 Best regards Neil

1 0

[math-fun] continued fraction to represent P as x^2+K*y^2 for K=1, 2, 3, 4, 7
by Warren Smith 17 Jan '12

17 Jan '12

Let P>3 be a prime and let K be in {1,2,3,4,7}. P has a representation as x^2+K*y^2 with x,y>0 integers in these cases: * If K=1: iff P=4*m+1. This is the case P=sum of two squares. * If K=2: iff P=8*m+1 or 8*m+3. * If K=3: iff P=6*m+1. This and the preceding two were understood by Euler and Fermat. * If K=4: iff P=4*m+1. This one is basically the same as K=1. * If K=7: iff P mod 28 = 1,9,11,15,23, or 25. Further, whenever P is prime and such a representation exists, it is unique. Further, if N is nonprime with GCD(N,6)=1 then you can factor N into primes and/or squared primes, represent them, then multiply the (+-x+-i*sqrt(K)*y) complex number forms of the reps together to represent N in all possible ways. This also allows you to rapidly count the number of representations once you know N's prime factorization. For every other K>0, the class number of the positive quadratic forms with the same discriminant as x^2+K*y^2 exceeds 1 so that unique factorization in the complex number field fails so that the preceding paragraph fails. Now, to FIND the unique representation of prime P>3 as x^2+K*y^2 with x,y>0 integers (K fixed), do the following. 1.solve for d so that d^2 + K is divisible by P and 0<d<P/2. [Thjs can be done fast with Shanks-Tonelli algorithm.] 2.perform the Euclidean algorithm on (d,P): q = P; LoopForever{ if( P-d*d is K times a square ){ output the representation of P = d*d+K*square and stop. } t = d; d = q mod d; q = t; } I claim this is guaranteed to work to find the rep whenever P is prime, P>3, K in {1,2,3,4,7} and P is such that a rep exists; and in these cases the loop only gets iterated a logarithmic number of times at most. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Peter Luschny's gamma function approximation-formulas collection
by Bill Gosper 16 Jan '12

16 Jan '12

wds> http://www.luschny.de/math/factorial/approx/SimpleCases.html Luschny describes efforts like Gosper's latest as "pimp my formula" :) ------- Ok, here's 34.6 digits on z>12, nine BFs. http://gosper.org/munafacmu34.png I'll bet we can do better with a different shape to the rational function. --rwg

1 5

[math-fun] History of Factoring - an overlooked paper
by rcs＠xmission.com 15 Jan '12

15 Jan '12

Franz Lemmermeyer has uncovered a neglected early paper on factoring. This is from 1858, and may have been 'lost'. Dickson's History references Simerka's paper as an explanation of composing BQFs, but he apparently overlooked the factorization of R17. http://arxiv.org/abs/1201.0282 Simerka - Quadratic Forms and Factorization: Franz Lemmermeyer In this article we show that the Czech mathematician Vaclav Simerka discovered the factorization of (10^17-1)/9 using a method based on the class group of binary quadratic forms more than 120 years before Shanks and Schnorr developed similar algorithms. Simerka also gave the first examples of what later became known as Carmichael numbers. Some other factoring work in the same era ... Lucas was working on showing M127 prime 1857-1876. Around this time, people were working out how to augment the converse of Fermat's Little theorem to test primality. M61 was a good target, since M61-2 = 2*M60 has an easy factorization. In 1874, the philosopher/economist/logician Jevons offered 8616460799 as an example of a number whose factorization would never be known except to himself. Lehmer factored it in 1903. Cole's silent presentation of the factors of M67 was in 1903. When asked how hard it was, he is said to have replied 'three years of Sundays'. It's unclear what method he used. Rich

1 0