Euler's Fizzbuzz (2020)

Post by perl4ever » Wed, Mar 17, 2021, 4:40 AM UTC

uuidgen wrote: post #46

Qub3d wrote: post #4

The fundamental mathematical concepts revealed in this answer, especially the use of Euler's totient theorem, are worth pondering because it is this branch of modular arithmetic that Diffie and Hellman first proposed, and then Rivest, Shamir, and Adleman concretely used to produce, well, RSA: https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Operation Sadly, quantum supremacy may mean this form of cryptography will so…

I don't believe "quantum computing" will get us any step closer to breaking RSA. Similar how complex number theory didn't allow us to draw a square with area of -1. To break RSA-N you need a superposition of all the numbers up to 2^N, AFAIK there is even not a hint how to approach it physically.

Didn't I read somewhere that quantum computing basically gets you a factor of 2, like 2^(N-1)? It's a lot but at the same time it's just a bit.

Post by svat » Wed, Mar 17, 2021, 4:25 PM UTC

philcrissman wrote: post #79

svat wrote: post #53

Earlier quoted context omitted.

This is a nice post; thanks for writing it! (A minor thing: the margin notes completely disappear on mobile, i.e. at width of 760px or less.) You probably know this already, but I'd think of this the following way. There are two main mathematical ideas involved here: • The first, easy to underrate because it can seem "obvious", is the Chinese remainder theorem. This, for instance, here implies that any function of th…

Thanks! Re the margin notes, the footnote numbers are clickable to toggle them inline when the width is too small... I should add a bit of color or underline to them in the css so that this is easier to intuit. :/

Ah, clicking the footnote numbers worked for footnotes 1 to 4, but not for 5 and 6.

BTW, for the question “Where do the constant values 0, 6, 10, and 1 come from?”, though it's implicit in the post, it is useful to note explicitly that as x^4 takes only the values 0 or 1 either mod 3 or mod 5, these four possibilities—namely (0,0), (0,1), (1,0), (1,1)—precisely account for those values:

    (0 mod 3) and (0 mod 5) ⇔ (0 mod 15)
    (0 mod 3) and (1 mod 5) ⇔ (6 mod 15)
    (1 mod 3) and (0 mod 5) ⇔ (10 mod 15)
    (1 mod 3) and (1 mod 5) ⇔ (1 mod 15)

This would also simplify the post considerably maybe, as much of the algebra wouldn't be needed.

Re: Euler's Fizzbuzz (2020)

Re: Euler's Fizzbuzz (2020)