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).

44 Replies

3 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

~81 more replies

d@nny disc@

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

d@nny disc@

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

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

looking up ABNNR and AEL codes to find this truly impressive disclaimer statement in a paper

This work was not supported in part by Microsoft Research fellowship, NSF Grant CCF0514167, IAS/DIMACS post-doctoral fellowship.

.....not supported? i was vaguely confused until the next line:

A. Akavia is with the School of Mathematics, Institute of Advanced Study, Princeton NJ, USA akavia@ias.edu
R. Venkatesan is with Microsoft Research, Redmond WA, USA andBangalore India. venkie@microsoft.com

and i was like oh these are like cartoon villain characters. of course they'd love to put shit like that in the disclaimer about accepting money from the government to fund their own research

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

once i understood princeton university as a fundamentally evil force in the world everything made much more sense

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

Furthermore, we present an error reduction algorithm for these codes. That is, an algorithm that, given a codeword corrupted by adversarial noise flipping a constant fraction of its bits, outputs a message that agrees with the original message on at least (1 − ε)-fraction of its bits, for ε an arbitrarily small constant.

this is pretty thoughtfully designed!

(Here, following standard terminology, we refer to the non-binary code as the outer code and to the binary code concatenated with it as the inner code.)

yeah my message stream codes have pronouns get used to it

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

hey're using this term "binary linear code" and i think it just means "indefinite-length bit string" but the field of coding theory definitely gets my approval for being the first to actually care about representations of data across the system

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

ugh i really wanna apply to princeton to work on cryptography bc while i know they are possibly the most evil people on the planet, i also am confident that they will not be able to break my really simple and safe cryptosystems. and i feel they would let me do actually good mathematics because it would be good PR for them

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

i will admit though part of it is because i realilzed the flaw in godel's proof of incompleteness is that it's defined in the very limited logic of the integer system used by hilbert. and a system defined in a way without those restrictions could still prove a statement of its own self-consistency as well as completeness

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

god damn i forget princeton has such good PR https://ece.princeton.edu/people/david-wentzlaff this guy's students appear to be actually developing operating systems???? crazy

https://ece.princeton.edu/people/david-wentzlaff

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

i feel like a phd advisor from MIT would be terrible for my mental health though

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

https://www.princeton.edu/~wentzlaf/

Before joining Princeton, he completed his PhD and MS at MIT and was Lead Architect and Founder of Tilera Corporation, a multicore chip manufacturer now owned by Mellanox.

back when i was still configuring my own kernel build (earlier this year) mellanox was one of the vendors i specifically refused to enable support for

David Wentzlaff

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

chip manufacturing is cool though

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

this guy's page is funny https://ece.princeton.edu/news/sharad-malik-named-inaugural-member-acm-sigsoft-academy nobody else in the world has this opinion except me but i find the SAT/SMT framework to be fundamentally engineered for enclosure/monopoly/fascism (not suprising, it's princeton)

but answer set programming is cool as SHIT because it lets you write universal quantifier expressions and then lets the computer do the work for you instead of having a million weird failure modes!! https://potassco.sourceforge.net/book.html

Potassco - the Potsdam Answer Set Solving Collection

https://ece.princeton.edu/news/sharad-malik-named-inaugural-member-acm-sigsoft-academy

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

so yes i do have a favorite logic programming paradigm and logic programming can be active engineered to resist systems of enclosure and accumulation

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

everything is political and that's fucking awesome

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

god i forgot reading the princeton site is so funny https://ece.princeton.edu/news/mittal-receives-ip-accelerator-award-improve-network-security this guy straight up getting a huge grant to do more and worse surveillance

https://ece.princeton.edu/news/mittal-receives-ip-accelerator-award-improve-network-security

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

Mittal, professor of electrical and computer engineering, proposes building a novel network monitoring framework, Layer7, to detect and mitigate malicious attacks.

omg i totally forgot about my anonymity network for message routing idea i would love to stunt on everyone with that

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

i also find it kind of cosmically funny that they're awarding him from the intellectual property accelerator fund when he's literally doing absolutely nothing new at all. sure it could be patentable but the patent wouldn't be valuable

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

i just want to fight every single fuckboy in hand to hand combat until i emerge as the supreme fuckboy who mathematically guarantees my work can't be misused to hurt anyone because it explicitly avoids encoding systems of enclosure

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

like one basic issue with the concept of "public-key cryptography" is that someone can steal the private key (the same one you use to sign messages all the time) and then now what?

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

in fact this susceptibility is a core assumption of the model. but we can address some of the flaws with that by incorporating a client-server model for the parts that require coordination (like putting your public key in a public place)

one thing i failed to realize (i figured this out when chatting with @alina) is that there's an intentional built-in assumption with "public key" that you're going to tie your cryptographic security to a real-world identity. and that's obviously extremely dicey

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

but the thing about diffie-hellman key exchange is that it is basically the only "primitive" operation that actually actts like a "primitive", i.e. doesn't pull you into assumptions that don't make sense for your trust and thread model (and in fact, it can be used to craft a cryptosystem, because it's such an atomic and simple operation)