February 2012 - mathfun@mailman.xmission.com

Re: [math-fun] We don't need no stinking factorizer to break RSA... duh!!!!!!!!!
by Phil Carmody 18 Feb '12

18 Feb '12

Quoth Eugene Salamin: > Buy FPGA board.? Buy FPGA programming software.? Program and > debug FPGA.? Write software drivers.? Test and certify > algorithm.? Enjoy your nice new pseudo RNG. > > Alternatively, buy Ivy Bridge computer.? Enjoy Intel's nice > new true RNG. VIA had true RNGs on x86-family processors a decade ago. FSL had true RNGs on ARM-family processors last decade. I suspect that TI had them 2 decades ago, as I know TI was throwing every feature Nokia wanted into their SoCs, and Nokia was patenting HW RNGs back in the 90s. Why the desire to be so late to the game? Phil

1 0

[math-fun] cubed squares
by Warren Smith 18 Feb '12

18 Feb '12

The cubed square with the most water-volume is just to use the entire square without any tiles. [Maximizes sum_j (s_j)^3.] Course, it is not so easy if you demand #tiles=27 (or whatever). More interesting in my view is to MINIMIZE sum_j (s_j)^3.

1 0

[math-fun] Universal point-set for polynomial rootfinding
by Warren Smith 18 Feb '12

18 Feb '12

http://mathlab.mathlab.sunysb.edu/~scott/Papers/Newton/Published.pdf This paper is quite interesting. Given any polynomial P(z) of degree=D such that we know all its roots lie within the unit circle, they describe a "universal" set of 2.22 * D * (lnD)^2 points such that Newton's method starting from those points is guaranteed to converge to all the roots of P. By "universal" I mean that this point set does not know or care what P is (aside from knowing its degree and knowing al its roots lie in the unit disk). The point set is: Let N=ceiling(8.32547*D*lnD) and M=ceiling(0.26632*lnD). Equispace N points around the perimeters of each of the following M circles centered at z=0: radius = (1+sqrt(2)) * ((D-1)/D)^((2*v-1)/(4*M)) for each v=1,2,3,...,M. That's all.

2 1

[math-fun] Fwd: How much water can a 'cubed square' hold?
by Stuart Anderson 18 Feb '12

18 Feb '12

---------- Forwarded message ---------- From: geoffrey morley <ghmorley(a)gmail.com> Date: Sat, Feb 18, 2012 at 5:29 PM Subject: How much water can a 'cubed square' hold? To: Stuart Anderson <stuart.errol.anderson(a)gmail.com> Stuart, Place a (solid) cube on each subsquare of the perfect squared squares of order 22, so that each subsquare is the base of a cube. http://www.squaring.net/sq/ss/spss/o22/spsso22.html Each structure now comprises 22 cubes. Fill each structure with as much water as it can hold. How many ponds does each structure have? Which structure's ponds hold the most water? See also http://en.wikipedia.org/wiki/Water_retention_on_mathematical_surfaces 22:110A(60,50)(23,27)(24,22,14)(7,16)(8,6)(12,15)(13)(2,28) (26)(4,21,3)(18)(17) 3 ponds, volume of water is 540+2404+80=3024. z=height of water level in pond above bases of cubes=15, covers cubes (3,12), v=volume of water=(15-3)*3^2+(15-12)*12^2=540; z=16, cubes (4,6,7,8,13,14), v=2404; z=22, cube (2), v=80. 22:110B(60,50)(27,23)(24,22,14)(4,19)(8,6)(3,12,16)(9)(2,28) (26)(21)(1,18)(17) 2 ponds, volume of water is 3534+80=3614. z=17, cubes (1,3,4,6,8,9,12,14,16), v=3534; z=22, cube (2), v=80. 22:139A(80,59)(21,38)(29,28,17,27)(7,10)(18,20)(4,3)(32,8) (1,31)(30)(24,2)(22) 3 ponds, volume of water is 1488+8800+27=10315. z=20, cubes (2,8,18), v=1488. z=27, cubes (3,4,7,10,17,21), v=8800. z=28, cube (1), v=27. 22:147A(55,44,48)(40,4)(52)(26,29)(23,3)(20,31,21)(5,47)(43) (9,17)(1,8)(32)(25) 3 ponds, volume of water is 1380+8204+576=10160. z=23, cubes (3,20), v=1380. z=25, cubes (1,5,8,9,17,20,21), v=8204. z=40, cube (4), v=576. 22:147B(59,43,45)(41,2)(47)(34,25)(21,37,8)(55)(22,12)(10,23) (32)(11,26)(19,4)(15) 4 ponds, volume of water is 660+3081+1856+156=5753. z=15, cubes (4,11), v=660. z=22, cubes (10,12,21), v=3081. z=37, cube (8), v=1856. z=41, cube (2), v=156. 22:154A(61,52,41)(11,30)(9,35,19)(46,24)(16,33)(22,2)(36,17) (50)(47,21)(5,31)(26) 2 ponds, volume of water is 6766+9640=16406. z=26, cubes (2,9,21,22,24), v=6766. z=30, cubes (11,16,17), v=9640. 22:172A(97,75)(22,53)(39,42,38)(9,44)(4,19,13,2)(36,3)(11) (33,16)(24)(1,18)(17) 4 ponds, volume of water is 480+2860+2700+7744=13784. z=17, cubes (1,4,16), v=480. z=19, cubes (2,9,11,13), v=2860. z=33, cube (3), v=2700. z=38, cube (22), v=7744. 22:192A(86,49,57)(41,8)(28,37)(19,9)(47,35,4)(31,14)(10,36) (17,26)(12,71)(62)(59) 1 pond, volume of water is 45549. z=36, cubes (4,8,9,10,12,14,17,19,26,28,31,35), v=45549. If the squares that are squared are all the same size (side = 1 unit, say), then the volume of water is 22:110A- 3024/110^3 = 0.002272 (3 ponds); 22:110B- 3614/110^3 = 0.002715 (2 ponds); 22:139A- 10315/139^3 = 0.003841 (3 ponds); 22:147A- 10160/147^3 = 0.003198 (3 ponds); 22:147B- 5753/147^3 = 0.001811 (4 ponds); 22:154A- 16406/154^3 = 0.004492 (2 ponds); 22:172A- 13784/172^3 = 0.002709 (4 ponds); 22:192A- 45549/192^3 = 0.006435 (1 pond). 22:192A has only one pond, but holds the most water! Obviously (think about it), no two ponds can have the same water level. Geoff Some obvious questions; Which 'cubed' squared square holds most water? ( This would be a candidate, http://www.squaring.net/gfx/5468o55TTF.png - found in 1940 by Tutte, Smith, Stone & Brooks) Which (normalised) 'cubed' squared square holds the record?

1 1

[math-fun] mu question
by David Wilson 18 Feb '12

18 Feb '12

Letting mu be the Moebius function, and nu be the Mertens function defined as nu(n) = SUM(k = 1..n, mu(k)) Then I notice [1] SUM(k = 1..n, mu(k)*[n/k]) = 1 [2] SUM(k = 1..n, nu([n/k])) = 1 where [x] is the floor of x. I wondered if there was any simple relationship linking [1] and [2], or perhaps some relationship to the Moebius transform a(n) = SUM(d|n; b(d)) <=> b(n) = SUM(d|n; mu(n/d)*a(d)).

1 0

[math-fun] We don't need no stinking factorizer to break RSA... duh!!!!!!!!!
by Warren Smith 18 Feb '12

18 Feb '12

front page of NY Times just featured this paper http://eprint.iacr.org/2012/064.pdf which is hilarious! Just when you thought you'd seen the ultimate in human stupidity...

8 10

Re: [math-fun] We don't need no stinking factorizer to break RSA... Duh!!!!!!!!!
by Phil Carmody 17 Feb '12

17 Feb '12

Quoth Joerg Arndt: > Get an FPGA board, implement a (deterministic) random number generator > (with _very_ long period), and XOR in unbiased (Neumann will do, and you can recurse on the asymmetric diagonal if you're desperate for bits.) > entropy from several independent > noise sources (on that FPGA board, say 5 such at $3 each > ("enterprise solution")). ... > Problem solved? No, people will not use it because they do not > realize how bloody important the "random" part is. Amen! "Random" is a minefield. One of my pet rants is against the ignorant users of the Mersenne Twister, as, almost without fail, they'll seed the MT with sometimes as little as 15-bit of entropy, and then happily assert they're using the best random number source known to man. (Not all users are ignorant. However, after inspecting about a dozen open source projects, I'd claim that over 92% of them are. Worst of all is when they're willfully ignorant, in the face of bugs being filed against their PRNG.) Phil

1 0

Re: [math-fun] We don't need no stinking factorizer to break RSA... Duh!!!!!!!!!
by Phil Carmody 17 Feb '12

17 Feb '12

Quoth: "Adam P. Goucher" > > Cryptographic keys must be generated using true randomness, and a > > lot of entropy worth of it, say 2000 bits worth. > > If there are n possible birthdays of equal probability, then the number of > people required for there to be a reasonable probability of shared birthdays > is O(sqrt(n)) -- for reasons based on Stirling's formula. Hence, if we have > Np? possible prime numbers that a random number generator could > produce, where N is a reasonably large number (10^6, or so) and p is the > number of people using this system, then there should be no intersection. > > Based on the current word population, 90 bits of randomness should be > ample to avoid collisions, not 2000. Unfortunately you're not just trying to avoid collisions. I'm sure we have some real number theorists on the list, who can turn my fluffy statement into something closer to the truth but I'm pretty sure that if you know half of the digits of each of the factors, then you can factor the composite. It might even be 1/3rd (but might be 2/3rds). For example, consider (Lenstra's?) Divisors in Residue Classes method of primality proving. (You prove a number prime by generating an exhaustive but empty set of proper divisors in a particular residue class.) So if all your entropy is squeezed into one end of the number (or middle, etc.), your number might be easily factorable. More concretely, consider nextprime(10^500+random(10^20)) * nextprime(10^500+random(10^20)) as a number with more than 90 bits of entropy, but absolutely useless as a RSA modulus. Phil

1 0

[math-fun] RSA keys...
by Warren Smith 17 Feb '12

17 Feb '12

>If there are n possible birthdays of equal probability,... Based on the current word population, 90 bits of randomness should be ample to avoid collisions, not 2000. --no. You are missing the point. The collisions were not the problem, they were the symptom of the problem. The problem was, generating too few keys. This means the KGB (or whoever planted that bogus not-very-random generator in NETSCAPE or whatever) can break your RSA "secrets" easily by searching a small space, whose definition is known to them. Way smaller than they were supposed to need to search. Unfortunately for the KGB, the world pop of 10^10 would mean to avoid birthdays they would need to make the space be 10^20, which would be too large for them to crack. So they made it smaller than 10^20, causing their plots to become revealable thanks to the Birthday effect. If you trust linux's alleged true-random bits and Intel's alleged true random bits, then fine, problem solved. I think in the case of Intel you really should trust them... probably... because a cheat engineered by the KGB in cooperation with Intel would be revealed by collision tests -- which they pass. Intel+KGB could be cleverer and weaken their randoms only when their hardware hack detected they were being used by a keygen code. This would be harder to detect, but still detectable, by the writers of the keygen code. If they tried.

2 1

[math-fun] Lattice posability of Heronian simplices - mea culpa
by Warren Smith 17 Feb '12

17 Feb '12

I had earlier posted a "proof" of this here in 3D and 4D. It's wrong. Then Fred Lunnon, whom I thought (due to miscommunication) had agreed with my proof for over a month -- surprised me by posting his paper proving this on the arXiv, and not crediting my earlier proof. However, the explanation is that Lunnon actually had detected that my "proofs" were bogus due to an exceedingly stupid error. This was revealed just now when I enquired of Lunnon. The error was, I had "E" and I had "new E" and got the two confused. Very dumb, but I somehow managed it. So anyhow, I retract my proofs. Even earlier, Lunnon himself had sent me email containing his own bogus proof, which I had pointed out the bogusness in by return email. Fortunately in that case, there was no miscommunication, i.e. we both realized the proof was wrong. To my credit, I then produced a new proof, but to my discredit, it was wrong. Then Lunnon has now produced a third proof, to his credit -- in 3D -- which hopefully is now right! Lunnon's new proof employs quaternion GCDs, which was an approach I had originally suggested and pushed to Lunnon... although in my bogo-proofs I had wrongly thought the need for them had gone away. I'm sorry this all happened and hope his latest proof is correct. As far as I currently know my other proofs about other Heronian simplex topics remain ok, and nobody has pointed out any errors or claimed-errors in them... yet...

1 0