May 2013 - mathfun@mailman.xmission.com

Re: [math-fun] Wieferich [pseudo]primes [stupid typo(s)]
by Bill Gosper 02 May '13

02 May '13

So 11 is a Wieferich prime base 112 and [31] is a Wieferich prime base 374. I don't know whether to thank everybody for silently correcting it in stride, or grumble that no one is paying sufficient attention. Whichever the case, last week I put another one past you. At the very end of the long "inconvenient observation" message, (Apologies: In[378] is confusing because ConfinuedFractionK uses {{0,num},{1,den}} style matrices, but st uses {{den,num},{0,1}}.) should be {{den,num},{1,0}}. Neil has actually found an OEIS sequence corresponding to one of those fractalish output vs input patterns, but I now think these are the wrong place to focus. More important to the number theory is what gets produced vs exactly when, which varies with tweaking the conversion algorithm(s). --rwg

1 0

[math-fun] Wieferich [pseudo]primes
by Bill Gosper 02 May '13

02 May '13

The Instant Google type-in anticipator for pseudop... proposed pseudopseudohypoparathyroidism. >>>> On Tue, Apr 30, 2013 at 5:06 PM, Bill Gosper <billgosper(a)gmail.com>wrote: >>>> >>>>> Wow. Nice. It appears that the base 2 6.7x10^15 search >>>>> https://cs.uwaterloo.ca/journals/JIS/VOL14/Klyve/klyve3.html >>>>> omitted pseudoprimes. A moronic Mma search thru 5.7G >>>>> is so far fruitless. Has no one tried this before? >>>>> --rwg >>>>> >>>> > rcs>If we vary the base, we can arrange for Wieferich pseudoprimes: Start >>>>> with the known base 2 psp 341: 2^340 = 1 (mod 341) while 341 = 11*31 is >>>>> composite. But 2^340 = 34783 (mod 341^2), so the "tens digit" is 102, >>>>> [34782/341]. We muck around with the tens digit: (2+341K)^340 (mod 341^2) = >>>>> 2^340 + 340 * 2^339 * 341K + stuff * 341^2. The coefficient of 341K is >>>>> effectively -1/2, so Set K=204 to zero out the tens digit from 2^340. >>>>> 69566^340 = 1 (mod 341^2) and 69566^341 = 69566 (mod 341^2). Rich ----- >>>>> Quoting Bill Gosper <billgosper(a)gmail.com>: >>>>> >>>>> Is it obvious that if n∈N and 2==Mod[2^n,n^2] then n is (a Wieferich) >>>>> prime? Why don't we just call A001220 Wieferich numbers? --rwg >>>>> >>>>> -- >>>>> >>>> FredH> > Any prime divisor of a "Wieferich pseudoprime" (i.e., a composite n >>>>> such that 2^n == 2 (mod n^2)) must itself be a Wieferich prime. A >>>>> proof can be found here (of all places): >>>>> >>>>> http://forums.xkcd.com/viewtopic.php?t=23397&p=699486 >>>>> >>>>> Julian reads the strip, but not the forums, and unaware of this item, privately sent a stronger thm: "I don't know whether the Wieferich property implies primality, but it does imply that all prime factors of the number are Wieferich primes. If 2^n=2 mod n^2, p|n is prime, and e is the order of 2 mod p^2 (p=2 doesn't work, since then 4 would divide n^2 and 2^n but not 2), then we must have e|n-1, so p does not divide e. Then e|p-1 and 2^p=2 mod p^2. Similarly, if n is divisible by p^k, we must have that 2^p=2 mod p^2k. Since this fails for known Wieferich primes and k>1, and 1093*3511 does not work, any composite example must be >10^20. Similar constraints hold for other bases–if a^n=a mod n^2 and p^k|n, then a^p=a mod p^2k." Julian Testing this on Rich's example, In[162]:= PowerMod[69566, 1, 121] Out[162]= 112 In[167]:= PowerMod[112, 11, 121] Out[167]= 112 In[163]:= PowerMod[69566, 1, 31^2] Out[163]= 374 In[165]:= PowerMod[374, 31, 31^2] Out[165]= 374 So 11 is a Wieferich prime base 112 and 37 is a Wieferich prime base 374. So it should be easy to collect lots of Wieferich primes to weird bases. Can these somehow point to some huge Wieferich pseudoprime base 2, yielding some new Wieferich prime, probably not the next? --rwg rwg> > Is it obvious that if n∈N and 2==Mod[2^n,n^2] then n is (a Wieferich) >>>>> prime? Why don't we just call A001220 Wieferich numbers? --rwg >>>>> >>>>> >>>>> The term "Wieferich number" has been used for n such that >>>>> 2^phi(n) == 1 (mod n^2); see A077816. >>>>> >>>>> OK, I guess we're stuck with Wieferich [pseudo]prime. Is {2}, the feasible Fermat exponent(s), in the OEIS? Perhaps there should be an entry for {}, the supposed infinitude of false positives from http://en.wikipedia.org/wiki/Baillie-PSW_primality_test , for a single example of which there stands a $620 cash bounty.

1 0

[math-fun] Conjugate gradient (Krylov) method & polynomials
by Henry Baker 01 May '13

01 May '13

If you've wanted to understand the conjugate gradient (CG) method (for solving sparse symmetric matrix Ax=b problems), and you haven't seen this paper before, you're in for a treat: http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf --- Question: If you carefully follow the CG algorithm, you're iteratively building up a real polynomial p_i(z) such that p_i(A) 'approximates' the matrix inverse 1/A ~ p_n(A). If CG goes to the end, the polynomial is related to the characteristic polynomial q(z): q(A) = 0 <=> q(A)-q(0)I = -q(0)I <=> (q(A)-q(0)I)/A = -q(0) (1/A) <=> (q(0)-q(z))/z/q(0) | z=A == (1/A) (i.e., the polynomial (q(0)-q(z))/z/q(0), evaluated at z=A.) (Note that q(0)=det(A)/=0.) What relation do these 'partial polynomials' of CG have to the characteristic polynomial of A ? Are these related to derivatives of the characteristic poly? Are these related to Sturm sequences/Pade approximations to the characteristic poly? Note that the particular CG 'partial polynomials' are dependent upon the right-hand side vector b, except when CG runs to the end, in which case the vector b drops out, leaving only the characteristic polynomial without any dependency upon b. Perhaps CG is a good (the best?) way to find the characteristic poly of a sparse matrix?

1 0

Re: [math-fun] ridiculously simple derivation (whose?) of Pythagorean triples
by Henry Baker 01 May '13

01 May '13

Here's an interesting application of 4Squares: creating 'trap doors' in RSA encryption. http://www.moi.math.bas.bg/oc2009/a26.pdf Hiding information in products of integers. Constantinos Patsakis, Nikolaos Alexandris {kpatsak, alexandr}(a)unipi.gr Department of Informatics, University of Piraeus Karaoli & Dimitriou 80, Piraeus, 185 34 Greece Sixth International Workshop on Optimal Codes and Related Topics June 16-22, 2009, Varna, Bulgaria pp. 157-162 Abstract. In this work we present a new SETUP for public key encryption algorithms that use products as part of their keys. Using the decomposition of an integer as a *** sum of four squares, *** enables us to create a backdoor on the products that if properly used, may lead their polynomial time factorization. At 10:24 PM 4/30/2013, Fred lunnon wrote: >Henry Baker has raised the matter of deterministic algorithms for >square-root (mod p) . > >The Bumby paper seems to have been published in the late 1980's, >after a burst of activity in this area. There does not appear to have >been much progress since: a 2010 paper by Tsz-Wo Sze at > arxiv.org/pdf/0812.2591 >implies that there is no known deterministic algorithm in time polynomial >in log(p). > >WFL

1 0

Re: [math-fun] ridiculously simple derivation (whose?) of Pythagorean triples
by Fred lunnon 01 May '13

01 May '13

Henry Baker has raised the matter of deterministic algorithms for square-root (mod p) . The Bumby paper seems to have been published in the late 1980's, after a burst of activity in this area. There does not appear to have been much progress since: a 2010 paper by Tsz-Wo Sze at arxiv.org/pdf/0812.2591 implies that there is no known deterministic algorithm in time polynomial in log(p). WFL >>On 4/30/13, Fred lunnon <fred.lunnon(a)gmail.com> wrote: >>> Solving >>> w^2 + x^2 + y^2 + z^2 = p , an odd prime, >>> is rather simpler than Bumby manages to make it look. >>> His final section mentions the Tonelli-Shanks algorithm for >>> computing square root modulo p . >>> >>> So armed with this algorithm, compute a solution of >>> a^2 + b^2 + c^2 = 0 (mod p) >>> in time order log(p) roughly; then set >>> Q = w + x i + y j + z k = GCD_L ( a i + b j + c k, p) , >>> where GCD_L denotes left-hand quaternion GCD . >>> Now ||Q|| = p , yielding a single solution. >>> >>> If all solutions are required, the simplest procedure is to continue >>> by >>> stepping around all p+1 points of the conic >>> a^2 + b^2 + c^2 = 0 (mod p) >>> in the projective plane over |F_p , starting from the solution found >>> above, >>> and converting each point via GCD with p as before. >>> >>> The resulting set {Q} comprises one representative from each >>> unit-association class on the right: taking products with >>> {1, i, j, k, -1, -i, -j, -k} >>> yields the complete solution set in time order p log(p) , >>> along with the cardinal 8(p+1) specified by Jacobi's theorem. >>> >>> Quaternion GCD is a natural extension of the Euclidean algorithm, >>> slightly complicated by non-commutativity, and potential non-termination >>> if both norms are even. Further details and program code are available. >>> >>> Fred Lunnon >>> >>> On 4/29/13, Henry Baker <hbaker1(a)pipeline.com> wrote: >>>> Bumby! Excellent! Just exactly what I wanted. Thanks, Neil! >>>> >>>> http://www.math.rutgers.edu/~bumby/squares1.pdf >>>> >>>> At 06:26 AM 4/29/2013, Neil Sloane wrote: >>>>>Entry A000118 in the OEIS has many references. See, in particular, the >>>>> Bumby reference. >>>>> >>>>>On Mon, Apr 29, 2013 at 9:14 AM, Henry Baker <hbaker1(a)pipeline.com> >>>>> wrote: >>>>>> I'm still on the hunt for a 'ridiculously simple' way to express a >>>>>> positive integer as 4 squares. >>>>>> >>>>>> Most presentations for the 4-square theorem focus on proving that it >>>>>> is >>>>>> possible, but don't provide very good algorithms for actually doing >>>>>> it. >>>>>> >>>>>> At 09:47 AM 4/26/2013, Dan Asimov wrote: >>>>>>>How does that work with quaternions H or octonions O ? >>>>>>> >>>>>>>You can't just switch one coefficient. (Or you can, but >>>>>>>then you're just operating in a single complex subspace >>>>>>>of H or O, so it's really the same thing.) >>>>>>> >>>>>>>--Dan >>>>>>> >>>>>>>On 2013-04-26, at 5:50 AM, Fred lunnon wrote: >>>>>>> >>>>>>>> Etc. for quaternions and octonions, where available ... WFL >>>>>>>> >>>>>>>> On 4/26/13, Warut Roonguthai <warut822(a)gmail.com> wrote: >>>>>>>>> I don't know who discovered this, but I know that Pythagorean >>>>>>>>> triples can >>>>>>>>> be obtained from the fact that |z^2| = |z|^2. This is similar to >>>>>>>>> the way >>>>>>>>> you can prove that the product of numbers representable as sums of >>>>>>>>> two >>>>>>>>> squares is also representable as a sum of two squares by using the >>>>>>>>> fact >>>>>>>>> that |z1 * z2| = |z1| * |z2|. >>>>>>>>> >>>>>>>>> On Fri, Apr 26, 2013 at 3:04 PM, Bill Gosper <billgosper(a)gmail.com> >>>>>>>>> wrote: >>>>>>>>> >>>>>>>>>> In[570]:= (1+2*I)/(2+1*I) >>>>>>>>>> Out[570]= 4/5+(3 I)/5 >>>>>>>>>> >>>>>>>>>> In[571]:= (1+3*I)/(3+1*I) >>>>>>>>>> Out[571]= 3/5+(4 I)/5 >>>>>>>>>> >>>>>>>>>> In[572]:= (2+3*I)/(3+2*I) >>>>>>>>>> Out[572]= 12/13+(5 I)/13 >>>>>>>>>> >>>>>>>>>> In[573]:= (1+4*I)/(4+1*I) >>>>>>>>>> Out[573]= 8/17+(15 I)/17 >>>>>>>>>> >>>>>>>>>> In[586]:= Simplify/@ComplexExpand[(a+I*b)/(b+I*a)] >>>>>>>>>> Out[586]= (2 a b)/(a^2+b^2)-(I (a^2-b^2))/(a^2+b^2) >>>>> >>>>>-- >>>>>Dear Friends, I have now retired from AT&T. New coordinates: >>>>> >>>>>Neil J. A. Sloane, President, OEIS Foundation >>>>>11 South Adelaide Avenue, Highland Park, NJ 08904, USA >>>>>Phone: 732 828 6098; home page: http://NeilSloane.com >>>>>Email: njasloane(a)gmail.com > >

1 0

[math-fun] Wieferich numbers?
by Bill Gosper 01 May '13

01 May '13

Wow. Nice. It appears that the base 2 6.7x10^15 search https://cs.uwaterloo.ca/journals/JIS/VOL14/Klyve/klyve3.html omitted pseudoprimes. A moronic Mma search thru 5.7G is so far fruitless. Has no one tried this before? --rwg rcs>If we vary the base, we can arrange for Wieferich pseudoprimes: Start with the known base 2 psp 341: 2^340 = 1 (mod 341) while 341 = 11*31 is composite. But 2^340 = 34783 (mod 341^2), so the "tens digit" is 102, [34782/341]. We muck around with the tens digit: (2+341K)^340 (mod 341^2) = 2^340 + 340 * 2^339 * 341K + stuff * 341^2. The coefficient of 341K is effectively -1/2, so Set K=204 to zero out the tens digit from 2^340. 69566^340 = 1 (mod 341^2) and 69566^341 = 69566 (mod 341^2). Rich ----- Quoting Bill Gosper <billgosper(a)gmail.com>: Is it obvious that if n∈N and 2==Mod[2^n,n^2] then n is (a Wieferich) prime? Why don't we just call A001220 Wieferich numbers? --rwg

2 1