Post by @hipsterelectron@circumstances.run

@hipsterelectron@circumstances.run 6 hr. ago

so i fouind this website from a guy who is way way way too fanatic about david hilbert and gauss. and he phrased gauss's "golden theorem" of quadratic residues a bit differently than others: https://archive.lib.msu.edu/crcmath/math/math/q/q044.htm

If p and q are distinct odd primes, then the congruence:
x^2 = q (mod p)
x^2 = p (mod q)
are both solvable or both unsolvable unless both p and q leave the remainder 3 when divided by 4 (in which case one of the congruences is solvable and the other is not).

33 Replies

4 Boosts

d@nny disc@

@hipsterelectron@circumstances.run 6 hr. ago

this is very directly translating the gauss theorem i literally think is just false into a method to attack diffie-hellman key exchange. and that's really weird!!

Quadratic reciprocity - Wikipedia

d@nny disc@

@hipsterelectron@circumstances.run 6 hr. ago

Privately, Gauss referred to it as the "golden theorem".[2] He published six proofs for it, and two more were found in his posthumous papers. There are now over 240 published proofs.[3]

usually this is not the kind of behavior i associate with a strong proof

d@nny disc@

@hipsterelectron@circumstances.run 6 hr. ago

Generalizing the reciprocity law to higher powers has been a leading problem in mathematics, and has been crucial to the development of much of the machinery of modern algebra, number theory, and algebraic geometry, culminating in Artin reciprocity, class field theory, and the Langlands program.

if that's true then all of mathematics is fucked too

d@nny disc@

@hipsterelectron@circumstances.run 6 hr. ago

i'm forking mathematics

~98 more replies

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

Quadratic reciprocity arises from certain subtle factorization patterns involving perfect square numbers.

everyone just absolutely refuses to avoid extremely abstract language like "is solvable" when making statements about discrete logarithms

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

after seeing the archmedes debacle i also feel that a lot of stuff fermat supposedly said was stuff gauss just made up and attributed to him

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

i also just really don't understand the framing of fermat's last theorem.

The proposition was first stated as a theorem by Pierre de Fermat around 1637 in the margin of a copy of Arithmetica. Fermat added that he had a proof that was too large to fit in the margin.

this definitely sounds like something someone made up and wrote in themselves

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

it's just flatly wrong to assume the "generalization" of "pythagorean triples" is to start cubing shit. that's just the fucking euclidean norm dudes!!!! if you stopped circlejerking over integer solutions for one fucking second you'd see that higher dimensions mean adding a new vector component!!!!!

but failson gauss decided yeah what if more dimensions meant cubic equations

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

i found this very ridiculous page from NIST on modular forms https://dlmf.nist.gov/23.15#i linked from the wikipedia page on modular forms https://en.wikipedia.org/wiki/Modular_form

Modular form - Wikipedia

DLMF: §23.15 Definitions ‣ Modular Functions ‣ Chapter 23 Weierstrass Elliptic and Modular Functions

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

now THIS is a really high-quality example of evil graph theory (from 2006) https://doi.org/10.1090%2FS0273-0979-06-01126-8

Expander graphs and their applications

...but it ALSO shows that the matrix view of graphs is WILDLY insufficient to capture their mechanics!!!

Bulletin of the American Mathematical Societysearch

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

Let A be an n×n matrix over the ﬁeld1 F. What is the least number
of gates in a circuit that computes the linear transformation x → Ax? Each gate is speciﬁed by two ﬁeld elements a and b. Such a gate receives two inputs x and y and outputs ax + by.

i.e. given a single input-output pair, can wee infer the underlying structure of the system, in some hardware circuit to perform a linear transformation A?

1 This problem is interesting for ﬁnite as well as for inﬁnite ﬁelds.

i.e. "this can be used for finite-field modular exponentation"

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

i hate it when people hide or act coy about doing evil shit. just say it right up front and maybe i will read your paper

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

they glaze up the fast fourier transform too. don't know why these kinds of people flock to FFTs like a moth to a lightbulb but clearly it excites them somehow

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

The technological implications of a Very Fast Fourier Transform, i.e. an O(n)-sized circuit that computes the transform (should one exist), are hard to overestimate.

i used to be on this side until i realized math loves us and math is on the side of justice

On the other hand, it would be a great theoretical breakthrough to establish a matching lower bound of Ω(n log n), or even rule out the existence of such a circuit with only O(n) gates.

you got it. coming right up

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

ohhhhh they're citing more evil graph theory

d@nny disc@

@hipsterelectron@circumstances.run 5 hr. ago

WTF THEY HAD ASYMPTOTIC RUNTIME FOR NUMA FIGURED OUT IN 1976????????? https://www.sciencedirect.com/science/article/pii/S0022000076800414/pdf?md5=9ad19c31757657dd445a077a46192f59&pid=1-s2.0-S0022000076800414-main.pdf

As a vehicle for exhibiting the kinds of complexity results that these graph- theoretic properties do imply, we introduce a random access model of computation with a certain cost for communicating between different locations.

cc @astraleureka valiant is someone spinrad taught in class and they make this sound so easy too

ScienceDirectScienceDirect (PDF)

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

For algorithms on this model that assume consecutive locations for the inputs we can resolve the
asymptotic complexity of some well-known arithmetic problems.

HOW DO THEY MAKE THIS SOUND SO EASY LMAO

The arguments used can be alternatively interpreted as supplying superlinear lower bounds for algorithms that are based on certain recursive splitting techniques but are otherwise unrestricted.

AAAAAAA LIKE OF COURSE YOU CAN STILL MAKE SURE TO KEEP MOST OF YOUR LOGIC IN THE STANDARD TURING REGIME SO IT STILL APPLIES MORE GENERALLY

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

We give upper and lower bounds of order n log n for the problems of computing polynomial convolutions and discrete Fourier transforms.

ahhhhhhh after reading https://en.wikipedia.org/wiki/Convolution i finally realized why discrete FFT is interesting to evil graph theory people: it lets you identify cyclic subgroups of a finite field efficiently!

Convolution - Wikipedia

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

cc @mildsunrise [i am not calling you evil here] i understand a little more why you were so passionate about the FFT a few months ago. that was really interesting work btw

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

it's just a little funny to see the author of a textbook works for the israeli war department and then it's published by cambridge university press. like oh this is some of that classic british colonialism

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

so this is basically how i was going to actually encrypt my messages was something like this http://cs-www.cs.yale.edu/homes/spielman/PAPERS/expandersIT.pdf they're calling it "expander codes" though and trying to expanders for error correction which is neat but i'm not sure i buy the hypothesis (which they are being very forthright about not knowing for sure)

View (PDF)

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

error correcting codes and encryption sound like opposites, but they are very very very closely related. imagine a cryptographic checksum or message digest as kind of the opposite of an error correction code, because a checksum squishes bits into fewer bits and hides stuff rather than adding extra bits in plaintext

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

i am waiting for someone else to have come up with my extremely terrible awful encryption method before and nobody's done it

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

it's such a grossly simple way to do encryption and i also think it may just be Really Good. but you WILL hate it

sean watters

@swatters@mastodon.social 4 hr. ago

@hipsterelectron one-time pad with (carrier)P(igeon)KI.

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

@swatters one-time pad is actually a terrible system and it's quiite literally an op when people mention that as the only unbreakable cryptosystem, for two reasons:

nobody who ever pushes that framing of the one-time pad as "ultimate/perfect" security actually explains what that would mean if the message was intercepted for example
you can in fact achieve something very close to that level of security with a completely different approach. the one-time pad is in this local maximum

the main reason for this is that (in my view) message encryption securtiy is actually much more permuting bits across boundaries than replacing text

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

@swatters llike if you were doing alan turing stuff in ww2 you would be reading intercepted messages with some parts unveiled (so you could extrapolate the rest of the text--that's kind of like a "chosen-plaintext attack" in today's terms but it's a little different).

but substitution is a fundamentally weaker primitive. consider: substituting the same symbol twice (a => b, b => c) is equivalent to just doing one substitution (a => c) [this is some kind of mathematical group operation but idk which one lol]

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

@swatters WHEREAS, if you chunk your bits into HIGHLY IRREGULAR (cruptographically-secure pseudorandom) size chunks, then reorder those chunks, then do it again (resulting in the same message length at all times), you actually do get more security. like shufflling a deck of cards

sean watters

@swatters@mastodon.social 4 hr. ago

@hipsterelectron so the key is what? the order of operations, chunk sizes, and position changes? is it the same number of chunks every time? does the encryption produce the ciphertext and the decryption key at the same time?

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

@swatters the key stream comes from a modular exponentiation process (literally just diffie-hellmann) and should be both independent of the message data stream as well as offline (not created interactively)

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

@swatters each round begins with recursive branching that takes 1-2 bits per branch (so instead of splitting the message up exactly halfway in length, a little more or less, up to like 1/3-2/3 depending upon the bits).

recurse on this until reaching some basic chunk size

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

@swatters this is the part i'm not quite sure about yet, because i don't fully understand all the scenarios where i might want to modify the message length (which in all cases means extending it).

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

@swatters hm i don't actually think i want to do the "down to basic chunk size" part at all actually, that was a new idea. and i also remembered i wanted to just do a single big split and then flip (i.e. take the uneven halves and write the second half from the start of your buffere and then the first half. so you have not changed length but you have split at an arbnitrary boundary and your data is out of order now..

i think one of the CSPRNG bits for that initial split and flip should go to deciding which half you then hit with a NOT (i.e. flip all its bits).