Post by @hipsterelectron@circumstances.run

@hipsterelectron@circumstances.run 4 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).

93 Replies

0 Boosts

d@nny disc@

@hipsterelectron@circumstances.run 4 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 4 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 4 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 4 hr. ago

i'm forking mathematics

d@nny disc@

@hipsterelectron@circumstances.run 4 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 4 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 4 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 4 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 4 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 3 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 3 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 3 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 3 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 3 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 3 hr. ago

ohhhhh they're citing more evil graph theory

d@nny disc@

@hipsterelectron@circumstances.run 3 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)