January 2012 - mathfun@mailman.xmission.com

[math-fun] Approximating the Gamma function via odd-symmetric series without use of log or exp
by Bill Gosper 23 Jan '12

23 Jan '12

Wow, this Remezes <http://www.tweedledum.com/rwg/recipoddremez.png> to mu=2*10^-36 with 14 parameters! --rwg wds> Approximating the Gamma function via odd-symmetric series without use of log or exp ==========================Warren D Smith===January 2012============================= You can also make the same approach work but now odd-symmetrically. Let F(x) = 1/GAMMA(x+1/2) [Half shift and reciprocation] as before. Then the even-symmetric product F(x) * F(-x) = cos(Pi*x)/Pi is known. If we know both the product and difference we can solve for the function value itself: a*b = p, a-b = d has solution: 1/a = 1/ [ -d/2 +- sqrt(d*d/4+p) ] = p / [ d/2 +- sqrt(d*d/4+p) ] So let us focus our efforts from here on on the odd-symmetric difference-function d(x) = F(x) - F(-x). Note d(0) = 0 , d(1/2) = -d(-1/2) = 1. Odd-symmetric Maclaurin series: d(x) = a1*x + a3*x^3 + a5*x^5 + ... n a[n] (probably too many sig figs) 1 +2.2155838077457420463420706011273861532011964034196 3 -0.8782068450071543970312933271566146210547472756753 5 +0.0597785511268765525562112629760526583628122029271 7 +0.0153465270962211928891443648520834538796743000868 9 -0.0020691028884223045620734315390504392488606408315 11 +0.0000368136041297145745345391282448961611113354311 this series has radius of convergence infinity. The coefficients are expressible in closed form, MAPLE knows how in terms of gamma, Pi, Riemann zeta, ln... but the formulas seem pretty nasty. Chebyshev series valid for x real with |x|<1/2 d(x) = b1*T1(2x) + b3*T3(2x) + b5*T5(2x) + b7*T7(2x) + ... n b[n] (probably too many sig figs) 1 1.026691148712964028143010336735095933411651823011179165757743251080660 3 -0.268221685958169797573564305029379545327023334950301175003624523012322e-1 5 0.129303162744591326555007007441325773066547121152841795798802532378070e-3 7 0.1732283652500262119684594728924325257327912284564252029346753804011e-5 9 -0.15582885160481449158005134567946714001039426528884456840721825850e-7 11 0.19215614127272524033878302481695622873236838653216308436905995e-10 13 0.125710846652610707719760530698850454093189146137737892751004e-12 15 -0.304239287982118987546845675936710370189616450492341901499e-15 17 -0.228543304071050074008778140993527912584044876007789732e-18 19 0.1026747421737886955434375472401652907750438705373650e-20 21 -0.3428129092655546076050020932259010193356887992e-25 23 -0.1521613621112612210432980081809452529820278380e-26 25 0.41130441677834000795641588393066361560497e-30 27 0.125353496337946321379878889536091985234e-32 29 -0.426948536716900856438110447660012316e-36 31 -0.654564249588552321735272510074462e-39 33 0.21758765315458092372227254347e-42 35 0.234927802069331038492894961e-45 37 -0.6580132252204947636736e-49 39 -0.6078105895687311484e-52

1 0

[math-fun] 6F5[-1/48]
by Bill Gosper 23 Jan '12

23 Jan '12

Fooling with more path invariant matrices last nite, the kids & I found HypergeometricPFQ[{1/2 - a, 1 - a, 1/2 + a, 1 + a, 23/14 + (2 a)/7 - 1/7 Sqrt[1 - 3 a - 3 a^2], 23/14 + (2 a)/7 + 1/7 Sqrt[1 - 3 a - 3 a^2]}, {5/4, 3/2, 7/4, 9/14 + (2 a)/7 - 1/7 Sqrt[1 - 3 a - 3 a^2], 9/14 + (2 a)/7 + 1/7 Sqrt[1 - 3 a - 3 a^2]}, -(1/48)] == (2 3^(3/2 + a) Sin[(a \[Pi])/3])/(a (11 + 12 a + 4 a^2)) I don't recall any F[-1/48]. Julian found 27 a which rationalize the parameters, e.g., HypergeometricPFQ[{46/43, 40/43, 49/86, 37/86, 883/602, 153/86}, {3/2, 5/4, 7/4, 281/602, 67/86}, -1/48] == 159014*3^(37/86)*Sin[Pi/43]/18827 There were three 3F2[-1/4] (which Macsyma could do), one 4F3, and no 5F4s. Along the way, he found the minor simplification puzzle 1 == 10*Sqrt[Pi]^3/(27*2^(2/3)*(1/3)!^2*(5/6)!*Sqrt[3]) and the unlikely looking 3*((4*Sqrt[3]*I + 1)/Sqrt[1 - I/4/Sqrt[3]] - (4*Sqrt[3]*I - 1)/Sqrt[I/4/Sqrt[3] + 1]) - 14*3^(1/4)*((47*Sqrt[3]*I + 24)/ Sqrt[4*Sqrt[3] - I]^5 - (47*Sqrt[3]*I - 24)/Sqrt[I + 4*Sqrt[3]]^5) == 121*Sqrt[Pi]^5/(288*2^(1/3)*(1/6)!*(1/4)!^2*(11/12)!^2*Sqrt[3]) We also accelerated Dixon's thm to get a three-parameter 7F6[-1/4]: HypergeometricPFQ[{a, b, c, 2*a - 2*b, -c - b + 2*a, (r + 3*c - b + 4*a)/10 + 1, (-r + 3*c - b + 4*a)/10 + 1}, {c - b + 1, (1 - b)/2 + a, -b/2 + a + 1, c + b - a + 1, (-r + 3*c - b + 4*a)/ 10, (r + 3*c - b + 4*a)/10}, -1/ 4] == (2*a - b)!*2^(2*b - 2*a)*(c - b)!*(c + b - a)!* Sqrt[Pi]/(a!*(-b + a - 1/2)!*c!*(c - a)!) r-> Sqrt[(3*c - b)^2 - 8*a*(2*c + b - 2*a)] a rational case of which is HypergeometricPFQ[{3/2 + a/2, 2 + a/2, 1 - c, 1 + a + 2 c, 1 + a/2 - c - (2 c)/a, 8/5 + a/5 - (2 c)/5 - (6 c)/(5 a), 1 + a/2 + 2 c + (2 c)/a}, {1 + a/2, 3/2 + a/2 + c/2, 2 + a/2 + c/2, 1 + a/2 - (2 c)/a, 3/2 - 2 c - (2 c)/a, 3/5 + a/5 - (2 c)/5 - (6 c)/(5 a)}, -(1/4)] == ( 2^(-1 - a - 2 c) Sqrt[\[Pi]] (2 + a + c)! (a/2 - (2 c)/a)! (1/2 - 2 c - (2 c)/ a)!)/(((3 + a)/ 2)! (a/2 + c)! (-(1/2) - c - (2 c)/a)! (1 + a/2 - c - (2 c)/a)!) --rwg

2 1

[math-fun] Approximating the Gamma function via odd-symmetric series without use of log or exp
by Warren Smith 22 Jan '12

22 Jan '12

Approximating the Gamma function via odd-symmetric series without use of log or exp ==========================Warren D Smith===January 2012============================= You can also make the same approach work but now odd-symmetrically. Let F(x) = 1/GAMMA(x+1/2) [Half shift and reciprocation] as before. Then the even-symmetric product F(x) * F(-x) = cos(Pi*x)/Pi is known. If we know both the product and difference we can solve for the function value itself: a*b = p, a-b = d has solution: 1/a = 1/ [ -d/2 +- sqrt(d*d/4+p) ] = p / [ d/2 +- sqrt(d*d/4+p) ] So let us focus our efforts from here on on the odd-symmetric difference-function d(x) = F(x) - F(-x). Note d(0) = 0 , d(1/2) = -d(-1/2) = 1. Odd-symmetric Maclaurin series: d(x) = a1*x + a3*x^3 + a5*x^5 + ... n a[n] (probably too many sig figs) 1 +2.2155838077457420463420706011273861532011964034196 3 -0.8782068450071543970312933271566146210547472756753 5 +0.0597785511268765525562112629760526583628122029271 7 +0.0153465270962211928891443648520834538796743000868 9 -0.0020691028884223045620734315390504392488606408315 11 +0.0000368136041297145745345391282448961611113354311 this series has radius of convergence infinity. The coefficients are expressible in closed form, MAPLE knows how in terms of gamma, Pi, Riemann zeta, ln... but the formulas seem pretty nasty. Chebyshev series valid for x real with |x|<1/2 d(x) = b1*T1(2x) + b3*T3(2x) + b5*T5(2x) + b7*T7(2x) + ... n b[n] (probably too many sig figs) 1 1.026691148712964028143010336735095933411651823011179165757743251080660 3 -0.268221685958169797573564305029379545327023334950301175003624523012322e-1 5 0.129303162744591326555007007441325773066547121152841795798802532378070e-3 7 0.1732283652500262119684594728924325257327912284564252029346753804011e-5 9 -0.15582885160481449158005134567946714001039426528884456840721825850e-7 11 0.19215614127272524033878302481695622873236838653216308436905995e-10 13 0.125710846652610707719760530698850454093189146137737892751004e-12 15 -0.304239287982118987546845675936710370189616450492341901499e-15 17 -0.228543304071050074008778140993527912584044876007789732e-18 19 0.1026747421737886955434375472401652907750438705373650e-20 21 -0.3428129092655546076050020932259010193356887992e-25 23 -0.1521613621112612210432980081809452529820278380e-26 25 0.41130441677834000795641588393066361560497e-30 27 0.125353496337946321379878889536091985234e-32 29 -0.426948536716900856438110447660012316e-36 31 -0.654564249588552321735272510074462e-39 33 0.21758765315458092372227254347e-42 35 0.234927802069331038492894961e-45 37 -0.6580132252204947636736e-49 39 -0.6078105895687311484e-52

1 0

[math-fun] Approximating the Gamma function via even-symmetric series without log or exp
by Warren Smith 22 Jan '12

22 Jan '12

Approximating the Gamma function via even-symmetric series without use of log or exp (but using sqrt and cosine) ==========================Warren D Smith===January 2012============================= Let F(x) = 1/GAMMA(x+1/2). [Half shift and reciprocation.] Then the even-symmetric product F(x) * F(-x) = cos(Pi*x)/Pi is known. If we know both the product and sum we can solve for the function value itself: a*b = p, a+b = s has solution: 1/a = 1 / [ s/2 +- sqrt(s*s/4 - p) ] = [ s/2 -+ sqrt(s*s/4 - p) ] / p Note for us the +- sign changes when x's sign changes, thus preventing F(x) from wrongly being even symmetric. So let us focus our efforts from here on on the even-symmetric sum-function S(x) = F(x) * F(-x). Note S(0) = 2/sqrt(Pi) = 1.128379..., S(1/2) = S(-1/2) = 1. Even-symmetric Maclaurin series: S(x) = a0 + a2*x^2 + a4*x^4 + ... n a[n] (probably to too many sig figs) 0 +1.1283791670955125738961589031215451716881012586580 2 -0.60900348841611068216370238307250126595327706534976 4 +0.40117091233557519976494358646090191877402434208538 6 -0.077697440910247074709804615656387720872711949327276 8 +0.0031307326305509859549042071031235561394059839823241 10 +0.00033007044645876790960938365344658406871455958329299 12 -0.000025637408145313339590477391674859646679049609798940 this series has radius of convergence infinity and gives you over 1 decimal per term, once it revs up. Not bad. The coefficients are expressible in closed form, MAPLE knows how in terms of gamma, Pi, Riemann zeta, ln... but the formulas seem pretty nasty. Chebyshev series valid for x real with |x|<1/2 S(x) = b0 + b2*T2(2x) + b4*T4(2x) + b6*T6(2x) + ... n b[n] (probably to too many sig figs) 0 1.06128021416184195755744883511279486310105592266570662506060510783873 2 -0.64152437934192797229552498479759593618768485117359381613700427217805e-1 4 0.29092677526038089329719837630334817453102073653264336290827255795697e-2 6 -0.3714620647551524243440434068657199748975962838655258078708791617057e-4 8 0.10163636208388614086441283321477130413815337257574084383480844642e-6 10 0.59291158040245953231577074770537791489904680950435069737753226e-9 12 -0.305157867631736055686720568881723513798138400380975541810644e-11 14 0.44513545729495127881935456940665312188830441896508085535e-15 16 0.1524786364625270677102897188967959495046769658412825416e-16 18 -0.1400941201553971044962512532302471662071644116029698e-19 20 -0.2851745012755828389691716435359123195188528447288e-22 22 0.3600820470720857936809914097648872787060815612e-25 24 0.2639903369752602613572830229951948536575891e-28 26 -0.4098407309916913596589789736282126814407e-31 28 -0.1452740903699932514280624009694405059e-34 30 0.2640523100792403872575823849289582e-37 32 0.563463271407374814567635972279e-41 34 -0.1078349899717743292405719179e-43 36 -0.178398654119405519004237e-47 38 0.297602323431721756704e-50 40 0.48138810046683331e-54 Incidentally, TnStar(z^2) = Tn(2z^2-1) = T[2n](z).

1 1

[math-fun] Mild puzzle
by David Wilson 21 Jan '12

21 Jan '12

Consider equations like the following: 0+4+8+27+96=135 with an addition expression on the left side and a sum on the right side, in which each digit occurs exactly once. If you don't like 0 as a term, you can usually find another expression with same sum value: 2+6+9+48+70=135 Suppose, however, that the 0 term cannot be eliminated. What is the sum?

3 4

[math-fun] Fwd: remezed spouge
by Bill Gosper 20 Jan '12

20 Jan '12

Privately (and maliciously), Warren suggested: On Sat, Jan 14, 2012 at 8:41 AM, Warren Smith <warren.wds(a)gmail.com> wrote: > you could perturb the constant "5" occuring twice in your formula, > to get presumably more accuracy from the same functional form. > rwg>Yeah, Mma tried to trick me into doing that when I said x+n->x+d[n]. (Except it missed the e^(-x-5).) Then later I tried making the 5 negotiable, and got stuck. But just now I tried with the other x+n unperturbed, and it worked! I need to investigate further. --Bill I just blew about 20hrs merely trying to analogously perturb the constant "4"! Remez takes a function, an interval, and an expression containing n undetermined coefficients, and attempts to determine those coefficients to minimize the maximum error over the interval (subject to your choice of smooth weighting function). It does this cleverly, not by directly trying to minimize anything with calculus, but rather by seeking to equalize the heights and alternate the signs of n+1 extrema of the error expression. (The n+1st degree of freedom being μ, the magnitude of those heights.) This is "equal ripple". You start the process either by guessing initial values of the n coefficients (and optimistically guess μ=0), and then hope to locate n+1 extrema, or by guessing the abscissæ of the extrema, and trying to solve for the coefficients. If you can get started with n+1 extrema, you iteratively alternate between determining the coefficients from these extrema, and then determining the new extrema from these coefficients. Convergence, once established, is usually quadratic! Officially, however, the approximating expression is assumed to be a polynomial or rational function. Other expressions void the warranty, e.g. the d(4) in the second Spouge expression <http://www.tweedledum.com/rwg/remspouge.png>. With great difficulty, working by analogy from a still smaller example, I managed to guess a set of abscissæ and coefficients yielding eight extrema. These successfully iterated to refined values. And then got stuck <http://www.tweedledum.com/rwg/stuckspouge.png>! Even though the abscissæ had improved, the ripples simply refused to equalize--FindRoot announced failure, even with MaxIterations-> 9999. But it also returned its partial results, which gave eight very unequal ripples, which required manual intervention to fully locate. Re-solving with these extrema and the partial results got very slightly closer. And after many manual iterations, FindRoot resumed success, finally delivering 1.3 additional digits reward for perturbing the "4", as illustrated. Perturb "5" Warren? Be my guest. --rwg

1 0

[math-fun] (no subject)
by Warren Smith 20 Jan '12

20 Jan '12

>R.Baillie: regarding the last point mentioned below, page 1402 of the >baillie-wagstaff "lucas pseudoprimes" paper mentions this: if n is a psp >base a, but not a strong psp base a, then we can factor n in the process >doing the psp test base a. >> This also tells us something that is rather remarkable which I have > not seen before: > REMARKABLE FACT: Pseudoprimes (i.e. hard cases for our > probable-prime test) are > easy to factor. > > One has to wonder what applications this may have... --it may be that my observation and the one Baillie points out in his paper (which by the way somebody posted here: http://mpqs.free.fr/LucasPseudoprimes.pdf ) are in some sense the same observation (disguised). I think the underlying reason for these is that if you can find the multiplicative order of some y mod N, i.e. find r so that y^r=1 mod N then it is easy to factor N, i.e. GCD( y^(r/2) +- 1 , N ) will often factor N if r is even, which it is going to be. [If factor is trivial then try another y.] This is just the X^2-1=(X-1)(X+1) trick. For Fermat-style pseudoprimes that keep pretending to be prime, you can figure out the multiplicative order of numerous y mod N so you can factor N. So Carmichael numbers and Fermat pseudoprimes always are easy to factor. Now going to the polynomial world where pseudoprime tests now are based on polynomial(x) powers (mod both a pseudo-irreducible polynomial and mod N)... I suppose we could use the same trick but with polynomial GCD to, for such pseudoprime N, rapidly find polynomial(x) factors of the modulus polynomial, thus proving it really was not irreducible, thus proving N really was not prime. But I am not seeing how to deduce a factor of N itself. I guess this also explains to me a way to make a "strong" version of my "Galois test"... those polynomial GCDs all must be scalars or else we know N composite.

1 0

[math-fun] Totally different/new simple probable-prime test... shows pseudoprimes are easy to factor
by Warren Smith 19 Jan '12

19 Jan '12

GIven odd N>10 we wish to test for primality. 0. By trial division make sure N has no small prime factors. [If does, stop here.] 1. Generate a random x mod N. If GCD(x,N) is not 1 then you have factored N and are done. 2. Find its square s=x^2 mod N. 3A. Employ the Shanks-Tonelli (randomized) algorithm to find a square root y of s so that y^2 = s mod N. That algorithm is described here http://en.wikipedia.org/wiki/Tonelli–Shanks_algorithm This runs in O( (logN)^2 ) modular multiplications on average for random x mod N, but only O( logN ) multiplications if N-1 is not divisible by a very large power of 2. Also you can make sure the runtime is O(logN) multiplications (regardless of N) by using Cipolla's algorithm instead of Shanks-Tonelli, http://en.wikipedia.org/wiki/Cipolla's_algorithm All the randomness is is in step 2 of wikipedia's version of the ST algorithm (& a similar comment applies to Cipolla): you choose z randomly until finding z such that JacobiSymbol(z|N) = -1, which should succeed (N-1)/(2N) of the time if N is prime. (It also should succeed very nearly half the time if N is composite with no small prime factors.) Thus Wikipedia's step 2 is expected to run in 2 trials on average for either prime or composite N. 3B. I do not recommend this, but alternatively to 3A, one instead could employ the Schoof (deterministic, based on elliptic curves) algorithm to find such a squareroot y. That algorithm is described Rene J. Schoof: Elliptic curves over finite fields and the computation of square roots mod p, Maths. of Comput. 44,170 (1985) 483-494 pdf here: http://www.mat.uniroma2.it/~schoof/ctpts.pdf mucho errrata pdf here: http://www.mat.uniroma2.it/~schoof/schooferr.pdf and Schoof claims it runs in O( (logN)^9 ) bit operations using "slow arithmetic" for both numbers and polynomials as opposed to FFT-based "fast arithmetic" which would speed it up to O( (logN)^6.01 ) bit-ops. 4. Note, Shanks-Tonelli/Cipolla and Schoof both assume that N is prime in order to find the square root. If N is not prime, the "root" they find may be wrong, or at some point inside the algorithm we will do something illegal like divide by 0 or an assert may fail. Either way, "N is definitely composite" and stop. 5. If N is prime, there are exactly two square roots: x and N-x. If N is composite, then there must be at least 4 square roots, and since in step 1, x was random, there is no way for Shanks-Tonelli or Schoof to "know" that x was "the" root, as opposed to whatever root they were instead finding. My point is that they therefore must find a root y other than x and N-x, at least 50% of the time. If that happens then GCD(x-y, N) and/or GCD(x+y, N) will yield a nontrivial factor of N so "N is definitely composite" & stop. 6. If however y=x or y+x=N then we go back to step 1 for another test. 7. After K loop-iterations of steps 1-6, any composite N should have been detected with probability>=1-2^(-K). Therefore either N is prime, or we have been very unlucky in our choice of random numbers. --- This whole test is comparably efficient to a Miller-Rabin test (up to a constant factor) for random N. However, I think the constants are worse for this test than for Miller-Rabin. Does it have any advantages over Miller-Rabin? The only benefit I can see is that in the hard cases for this test, i.e. where the square-rootings succeed, it produces factors of N, which is kind of compensation for the fact that it is having a hard time on that N. This also tells us something that is rather remarkable which I have not seen before: REMARKABLE FACT: Pseudoprimes (i.e. hard cases for our probable-prime test) are easy to factor. One has to wonder what applications this may have... -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] "Galois test": new(?) class of compositeness tests based on two polynomials A(x) and B(x)
by Warren Smith 19 Jan '12

19 Jan '12

"Galois test": new(?) class of compositeness tests based on two polynomials A(x) and B(x) ===========Warren D. Smith-=============January 2012===================================== The following tests are intended to try to further-exploit the observation R.Baillie made that the pseudoprime (failure) sets for the Lucas and Miller type tests, tend to be "better than statistically independent" indeed actually "mutually avoiding." I am going to propose an infinite family of tests based on a pair of degree-k polynomials. It is infinite because k=2,3,4,5,... are all possible. In the case k=2 the test is pretty much like the Lucas test. There is no case k=1, but we will just say as a special case that k=1 is the Miller-Rabin/Fermat test, since that is the spirit if not the letter of the law. These tests can probably be improved to make them "strong" in the same way Miller-Rabin improved the simple Fermat test to make it "strong." However, I have not thought about that and will only present the "weak" tests here. THE SCENARIO: Let N>10, N odd, be a number we want to test for primality. Let k>1 be a small integer. THE "DEGREE-k GALOIS TEST": 1. Generate suitable random polynomials A(x) and B(x). B(x) being "suitable" means: * degree(B)=k * Coefficients of B are integers mod N * B is monic (i.e. coefficient of x^k is 1) * GCD(N, B(0)*discriminant(B(x),x)) = 1 [if not, then N is factored and we're done], Simpler criteria could be used here is you do not want to program discriminants, i.e. just B(0) is nonzero with GCD(B(0), N)=1 suffices. Discriminants might matter in a future "strong" version of this, though. * B(x) is "pseudo-irreducible" mod N, i.e. passes the irreducibility test below which would if N were prime be a proof of irreducibility. 2. The irreducibility test I had in mind is M.Ben-Or's [SFOCS 22 (1981) 394-398]: for j=1..floor(k/2) do{ G(x) = PolynomialGCD( B(x), x^(N^j) mod B(x) - x ) mod N; if G(x) is not 1 then "B is reducible" and stop; } Conclude "B(x) is irreducible mod N." This is valid if N is prime. [Note inside the loop you can repeatedly keep raising the power of x you had before, to the Nth power.] 3. Now, once you've produced A(x) and B(x) (by random trial) meeting the above conditions, we are ready to test N: for j=k-1 down to 1 do{ If PolynomialDegree( A(x)^((N^k-1)/(N^j-1)) mod B(x) mod N ) >= j then "N is definitely composite" & stop. } 4. Loop back to step 1. 5. If survive enough loop iterations of steps 1-4 then "N is probably prime." RUNTIME: If N is prime, then the fraction of random poolynomials which are irreducible is known to be >=1/k. Hence <=k random trials of steps 1-2 should suffice on average to find a suitable B(x). Ditto for A(x). Reviewing the exclusion argument underlying this, it seems to me that if N is composite then this runtime upper bound can only become more true. So the entire test is polynomial expected time and comparable to O(k^3) Miller-Rabin tests if we use "slow" polynomial arithmetic. And more like O(k^2.01) using "fast." [In practical use I think k would be small like k=2,3,4,5 only.] WHY IT WORKS: If N is prime, then the polynomials modulo N modulo any monic irreducible B(x) of degree(B)=k form the Galois field with N^k elements. The N^k-1 nonzero elements form a *cyclic* multiplicative group (theorem of Galois). Hence raising anything nonzero to power N^k-1 mod B(x) mod N has to yield 1. (Which our step 3 did not bother to test, but one could add that test if wanted.) Also, the cycle must include the entire subgroup of N-1 nonzero scalars, of N^2-1 nonzero polynomials of degree<=1, of N^3-1 nonzero polynomials of degree<=2, etc. Hence anything nonzero raised to the power (N^k-1)/(N^j-1) mod B(x) mod N has to yield a member of this (N^j-1)-element subgroup. I'm only particularly interested in the test with j=1, but since doing all the other tests with j=2,3,...,k-1 can also be done at basically no extra cost as a side effect of doing the test with j=1, I threw them in too. THE EXPONENT: Define E = E(k,N) = N^(k-1)+N^(k-2)+...+N^2+N+1 = (N^k-1)/(N-1). For example E(3,7)=7^2+7+1=57. This is the exponent used in the test with j=1 that I'm most interested in. CAN THIS BE MADE "STRONG"? It we understood nonscalar squareroots of scalars then if E=v*2^s with v odd we could examine the exponents v, 2v, 4v, 8v,..., E, to see if they met stronger criteria. THE HOPE FOR INDEPENDENCE/AVOIDANCE: My intent/hope/conjecture in designing this test is that degree-2 and degree-3 Galois tests and the Miller test all ought to fail "independently" (or, even better, the failures should "avoid" each other)... indeed hopefully all Galois tests with different k should have "independent/avoiding" bad-N failure sets. The reason for this hope is that (i) the exponents E(k,N) with different k all are going to be relatively prime in general, aside from factors of 2 and (ii) hope seems empirically to be true for k=1 and 2, e.g. there are now claimed after a large computation to be zero failures of one Miller (base=2) test combined with one Lucas/Baillie test for all N<2^64. [This totally is the opposite of the empirical fact that failing a Miller test makes other Miller-failures become MORE likely, i.e. dependence with positive correlation.] If so, then given Erdos's conjectures about pseudoprime counts below N ultimately behaving like N^( 1 - PositiveConstant* lnlnN / lnlnlnN ) it would follow from independence/avoidance conjecture that employing O(lnlnN) Galois tests all with different k's would presumably be strong enough so that only a finite set of bad (composite, but appearing prime) N could exist. This would suggest time equivalent to O((lnlnN)^3.01) Fermat tests suffices to rigorously test primality of N. This is surely beyond hope of proof at present, but (lnlnN)^O(1) is a very impressive conjecture, much stronger than Rabin/Miller's O(lnN) or O(lnN)^2. WHAT IS THE CONNECTION TO GRANTHAM'S "FROBENUS PSEUDOPRIMES"? His Frobenius and my Galois tests seem to have something to do with each other. It looks like mine is substantially faster. He has a "strong" notion, while I have not devised a comparable notion. He has not discussed the "independence/avoidance" hope which was my whole motivation, but he does discuss "Carmichael"esque numbers, proving they must have at least k+2 prime factors. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Alan Turing Centenary Cryptography Competition
by Henry Baker 19 Jan '12

19 Jan '12

The Alan Turing Centenary Cryptography Competition is a cryptography competition aimed at school children in Years 7-11 to celebrate his centenary. It is organised by the School of Mathematics at the University of Manchester. The story follows the adventures of Mike and Ellie, two children who get caught up in a race around Manchester, solving a number of secret codes, as they hunt for the long-lost 'Turing Treasure'. The competition will run from 9th January 2012 to 16th April 2012. There will be 6 chapters to the story and an epilogue. Each chapter contains a code that you will need to solve. The codes get harder as the competition progresses. We aim to release each chapter fortnightly on Monday afternoons at 4pm, according to the schedule below. As soon as your team have cracked the code, you should submit the code word to the competition website using the appropriate link in the left menu. There is a leaderboard on the website, so that you can see how your team is doing compared to others. See below for the scoring system. http://www.maths.manchester.ac.uk/cryptography_competition_2012/

1 0