February 2012 - mathfun@mailman.xmission.com

Re: [math-fun] The new RSA break -- request for circumspection.
by Ray Tayek 15 Feb '12

15 Feb '12

At 10:18 AM 2/15/2012, you wrote: > .. So if that's the cat you're thinking of, the bag thoroughly empty. http://it.slashdot.org/story/12/02/15/1540212/factorable-keys-twice-as-many… >On Wed, Feb 15, 2012 at 7:52 AM, Schroeppel, Richard ><rschroe(a)sandia.gov>wrote: > > > I'd like to encourage Math-Funsters to postpone discussing on the list > > the algorithms omitted from this paper for a month, till March 15. ... --- co-chair http://ocjug.org/

1 0

[math-fun] wrong word
by James Propp 15 Feb '12

15 Feb '12

The last sentence of the abstract for Dierk Schleicher's recent talk "Old and new about the dynamics of iterated transcendental functions" at Tufts may amuse you: Abstract: Much of holomorphic dynamics in the past 30 years has focused on iterated rational maps and especially polynomials, but especially in recent years there has been quite some progress on iterated transcendental maps. In particular, several conjectures of the 1980's ("classical" in this field) have recently been settled. This often leads to natural and at the same time surprising and even counterproductive results. Jim Propp

1 1

Re: [math-fun] The new RSA break -- request for circumspection.
by Phil Carmody 15 Feb '12

15 Feb '12

Quoth Schroeppel, Richard: > I'd like to encourage Math-Funsters to postpone discussing on the list > the algorithms omitted from this paper for a month, till March 15. Are you going to request DJB to withdraw his 2004 paper that describes how to do this too? The other team who've repeated Lenstra's results apparently used DJB's algorithm. Paul Leyland (see acknowledgements in the Lenstra paper) unwittingly squeezed an alternative algorithm with a very similar Big-Oh out of me today, again in a public forum. So there are at least 2 cats roaming around not in a bag any more. Phil

1 0

[math-fun] RSA keys, randomness, and idiots
by Warren Smith 15 Feb '12

15 Feb '12

Generating keys with a pseudorandom number generator, no matter how good, is absolutely 100% unacceptable. Cryptographic keys must be generated using true randomness, and a lot of entropy worth of it, say 2000 bits worth. (Which could then be piped thru a pseudorandom generator if desired, but the true randomness must be present at bottom.) Obviously, some idiot decided to generate keys using the "time of day" or something asinine like that as the source of "true random bits." Then they installed this code inside netscape or some other piece of common software. Paper found of around 2 million keys examined, about 0.2% of them involves identical prime factor to some other key. In other words, the aggregate key generators out there, feature a "random prime generator" that 0.2% of the time, stays within a fixed subset containing about 10000 primes only. This data also is compatible with the (presumably untrue) theory that there is only one random prime generator out there and it generates in total no matter how many times you invoke it, only 10^8 or 10^9 different primes, indicating it only employs about 27-30 bits of true randomness. A completely trivial collision test on whatever generator it was, would have revealed this but obviously was never run (if accidental) -- or this was an intentional move designed to allow the NSA or somebody to break security. Is the US Govt safe and only amateurs unsafe? Ridiculous baseless assertion. First, I assure you that this generator was written by professionals and installed in a professional piece of common software. Second, the US govt is now known to have controlled their military drone flights using entirely unencrypted signals for years (and for all I know still do so). The lesson here is: always assume the users/implementors of cryptography are beyond stupid, and will intentionally do the worst possible thing repeatedly thousands or millions of times. For example, suppose we consider the "one time pad" a well known "unbreakable" cryptosystem. It is now clear we can safely assume users will re-use the same old random bits as the "key" and hence we conclude as a corollary that the one time pad is an unacceptable cryptosystem.

2 1

Re: [math-fun] yet another triangle dissection puzzle
by Veit Elser 15 Feb '12

15 Feb '12

Any triangle can be dissected into three mirror-symmetric pieces. If we are limited to just two pieces, is the number of (non-congruent) triangles that admit a dissection (into mirror-symmetric pieces) finite or infinite? Veit On Feb 13, 2012, at 5:42 PM, Veit Elser wrote: > Okay, I'll try again: > > Which triangles can be dissected into two pieces, both of which are mirror-symmetric? > > On Feb 13, 2012, at 4:09 PM, Dan Asimov wrote: > >> Veit -- Can the word "just" be omitted without changing the meaning here, >> or is it in some way limiting the number of mirror-symmetric pieces >> that such a triangle can be dissected into? >> >> Thanks, >> >> Dan >> >> >> >> Veit asked: >> >> << Which triangles can be dissected into just two mirror-symmetric pieces? >> >> ________________________________________________________________________________________ >> It goes without saying that . >> >> _______________________________________________ >> math-fun mailing list >> math-fun(a)mailman.xmission.com >> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] We don't need no stinking factorizer to break RSA
by Phil Carmody 15 Feb '12

15 Feb '12

From: Warren Smith > 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... Shocking was the first word that came to mind, but hilarious followed shortly afterwards. If there's one thing that must be relearnt almost yearly, it's that, no matter how bullet-proof the maths is, the typical _implementation_ of crypto is often pathetically bad. Worse - it often remains bad after flaws have been highlighted. (E.g. the SSL library fiasco that Debian unwittingly uncovered, and suffered greatly from, a few years back still isn't satisfactorily fixed, despite it coming under worldwide scrutiny.) Phil

1 0

Re: [math-fun] the scale of our known universe
by Henry Baker 15 Feb '12

15 Feb '12

"Powers of Ten", by Charles & Ray Eames (yes, _that_ Eames, of the Eames chair, the Eames house, etc.) http://en.wikipedia.org/wiki/Powers_of_Ten http://en.wikipedia.org/wiki/Charles_and_Ray_Eames A copy of the Eames house is currently on display in the Los Angeles Museum of Art as part of the "Pacific Standard Time" exhibit(s), which involve many museums all over Southern California. I recently saw an excellent documentary about Charles & Ray Eames on PBS, in which "Powers of Ten" was prominently mentioned. Google Earth (nee Keyhole) got their idea from this movie. At 09:28 PM 2/14/2012, Rowan Hamilton wrote: >Thanks, I will show this to my 7 yo son! > >When I was a boy growing up in Texas I used to go to the Wednesday Night >Physics Movies at UT, and one of the movies they played was called >something like "Orders of Magnitude". It was a celluloid version of the >same thing shown here, and it was very good for teaching me the scales of >the universe when I was a young proto-physicist. > >Rowan. > >On Tue, Feb 14, 2012 at 9:18 PM, Simon Plouffe <simon.plouffe(a)gmail.com>wrote: > >> Hello, >> >> this flash animation (interactive) shows the scale >> of common things from the planck size to giant clusters >> up to the known universe which is 10^27 meters. >> >> Have fun, it's worth a look. >> >> http://www.htwins.net/scale2/ >> >> and a nice day. >> Simon Plouffe

1 0

[math-fun] the scale of our known universe
by Simon Plouffe 15 Feb '12

15 Feb '12

Hello, this flash animation (interactive) shows the scale of common things from the planck size to giant clusters up to the known universe which is 10^27 meters. Have fun, it's worth a look. http://www.htwins.net/scale2/ and a nice day. Simon Plouffe

3 2

[math-fun] Invitation to connect on LinkedIn
by Neil Sloane 14 Feb '12

14 Feb '12

LinkedIn ------------ I'd like to add you to my professional network on LinkedIn. - Neil Neil Sloane Fellow at AT&T Greater New York City Area Confirm that you know Neil Sloane: https://www.linkedin.com/e/e9nrug-gynsez21-i/isd/5927717953/gVXcKRqG/?hs=fa… -- You are receiving Invitation to Connect emails. Click to unsubscribe: http://www.linkedin.com/e/e9nrug-gynsez21-i/xSPi4T8taGHGbFmCcTW0_StU2AMEBQ4… (c) 2012 LinkedIn Corporation. 2029 Stierlin Ct, Mountain View, CA 94043, USA.

1 0

Re: [math-fun] min(x, y) and sorting without if()
by Phil Carmody 14 Feb '12

14 Feb '12

From: Joerg Arndt <arndt(a)jjj.de> > * Phil Carmody <thefatphil(a)yahoo.co.uk> [Jan 07. 2012 11:41]: > > From: Joerg Arndt <arndt(a)jjj.de> > > > These (branch-avoiding) techniques are "well known", see (fxtbook) > > > section 1.11 "Avoiding branches", pp.15ff where a warning of the form > > > "Your compiler may be smarter than you thought" is given. > > > > Shouldn't the warning be more Nuddsian? > > I do not parse "Nuddsian" here. Pertaining to Scott Nudds, the troll/loon who managed to force us to turn comp.lang.asm.x86 into a moderated newsgroup back in the mid-90s. His name is certainly not forgotten on comp.lang.c either, as he was a notorious cross-poster (he would deliberately try to get the two camps to fight each other). One of his weapons was the invocation of ... > > In C, such expressions are either unnecessary or UB, pure and > > simple. > > Reading UB as "useless b*ll****": "Undefined behaviour", as per the ISO C specification. In reality, it can equate to the same thing, as a sufficiently smart compiler can do exactly what you *don't* want in cases where UB is encountered. Many of the tricks are far from useless, but sometimes need a little bit of massaging before the C standard guarantees they will work. > There are a couple of tricks that prove useful in practice. > E.g., replacing > if ( (a<b) || (c<d) ) { ... } > by > if ( (a<b) | (c<d) ) { ... } > can be an improvement. Anything's possible. The latter has more re-ordering flexibility in some situations, so might fill bubbles in pipelines better. In reality, the programmer may not give a hoot which of the two comparisons expressions are evaluated first, but the short-circuit operator obliges him to express a preference. > One that I use regularly: > Replace > if ( (a<0) || (a>=n) ) { ... } > by > if ( (unsigned)a>=n ) { ... } Yup, that type of trick is a good one and it's safe. I've even gone as far as subtracting a lower bound before doing that, and then comparing >= range rather than >= max. > Yes, there are assumptions made, but I am not aware of > any _existing_ system where these do no hold. They certainly do exist. I perhaps immerse myself in a wider range of architectures than most, both at work and at home, so I am more aware of them. Shifting sign bits around on some DSPs will cause mayhem. Some Crays have trap representations for certain types which mean you can't hold certain intermediate values that would be useful. Worse, arch's with separate address and integer registers lose some of the efficiency of Knuth's dancing links, for example, in particular if their AGU is slow. > > Your compiler doesn't have to show smart behaviour at all - > > it may kill your cat if it wants to. > > Haven't spotted the part about cat slaughter in the standard yet :-) The problem is that it's not forbidden, so when the C standard says it imposes no restriction on what the implementation may do, that's implicitly giving it permission to kill kittens. The original absurd behaviour example was "nasal demons" (demons may fly out of your nose). That was hackneyed enough to have mutated to having the aforementioned Scott Nudds fly out of your nose. All such outcomes are to be avoided. > And quite a few people work extremely hard to make compilers smart. That's one of the things that makes UB so dangerous. They can be so smart that they realise that certain inputs would lead to UB, and therefore they only have to generate the correct results for the inputs that don't lead to UB, no matter what the consequences are in the UB case. GCC being smart regarding being able to not care about what happens when there's UB has introduced security holes into the linux kernel. It can just throw away a null pointer check, for example: http://lwn.net/Articles/341773/ I seem to have deviated both from mathiness and funness here, I apologise. It's just that I live, eat and breathe strict portable C currently, in particular other people's, and I'm hypersensitive to anything which is UB. Phil

2 1