Post · bonfire.cafe

@hipsterelectron@circumstances.run 6 hr. ago

the euclid infinite prime proof is fascinating for many reasons:

the action of first collecting all the known primes q_1, ..., q_k together by commutative multiplication and then adding 1 to it to get the new prime p is a mirror image of the prime field F_p in which p - 1 decomposes into subgroup prime ideals over finite fields with orders corresponding to the prime divisors of p - 1

so at some level even though euclid presumably was not thinking in terms of bits and bytes i do feel that ancient greek geometers were probably thinking closer to the terms of a finite field (consider bisecting an angle!) than anything gauss had ever assumed

15 Replies

2 Boosts

This comment is unavailable — it may have been deleted or is not visible to you.

@hipsterelectron@circumstances.run 3 hr. ago

and furthermore!

note where we might find an actually useful opportunity for cardano's otherwise-useless distinction between order and cardinality, as the pohlig-hellman algorithm calculates discrete logs (a serial process) over each subgroup—each subgroup can be computed in parallel, but the runtime will always be dominated by the order of the largest subgroup, and we can achieve asymptotic runtime and memory safety at the same time!

per hellman: https://www-ee.stanford.edu/~hellman/publications/28.pdf

The lemma shows that, neglecting logarithmic factors, the time-memory product can be held constant (since p^r p_i^{1-r} = p_i) as we go between the extremes of a table lookup and an exhaustive trial-and-error search.

and this piece advocates for q = 2p + 1 as well!

Pohlig–Hellman algorithm - Wikipedia

@hipsterelectron@circumstances.run 3 hr. ago

wow. this is kind of unbelievable. have you ever been told something like "asymptotic analysis doesn't incorporate knowledge of the CPU cache"?

we had extremely thorough analyses of asymptotic behavior with relation to CPU caching in fucking 1990!!!! http://courses.csail.mit.edu/6.895/fall03/handouts/papers/karlin.pdf

A snoopy caching multiprocessor system is a system in which a set of processors each with its own (snoopy) cache are connected over a bus to each other and to a large shared memory.

......it was, of course, specifically to do evil shit with timing attacks

There is a single address space used by all of the processors; each location in this space is called a variable. The memory space is partitioned into blocks, groups of variables of uniform size.

@hipsterelectron@circumstances.run 2 hr. ago

i cannot believe how badly the evil number theorists are whining. this was apparently the first attempt to introduce elliptic curve factorization onto lenstra's little trick https://maths-people.anu.edu.au/~brent/pub/pub102.html

Moreover, by the “Riemann hypothesis for finite fields” [12], the group order g = |G| satisfies the inequality |g − p − 1| < 2√p.

what is [12]? i'm not sure because it's in french and i can't find it. but sir come on

rpb102

~27 more replies

@hipsterelectron@circumstances.run 2 hr. ago

now i'm really banging on the doors https://en.wikipedia.org/wiki/Pigeonhole_principle this is just the axiom of choice again and i don't agree with that???

Pigeonhole principle - Wikipedia

@hipsterelectron@circumstances.run 2 hr. ago

it's also just ridiculously easy to disprove since this is the whole point of error-correcting codes??? it is not hard to describe a deterministic function that repeatedly selects overlapping bits if you like doing that sort of thing???

@hipsterelectron@circumstances.run 2 hr. ago

oh my fucking god i just found more lore about the guy who fucked up parsing theory https://en.wikipedia.org/wiki/Robert_W._Floyd

"The Compilation of Regular Expressions into Integrated Circuits"

HE ALSO FUCKED UP REGEX!!!! ENEMY NUMBER ONE!!!!

Robert W. Floyd - Wikipedia

@hipsterelectron@circumstances.run 2 hr. ago

this is also just very specifically the one "NASA" outpost they have that is specifically owned by the CIA. there's like a public autobiography about it somewhere

Floyd, Robert W.; Ullman, Jeffrey D. (1980). "The Compilation of Regular Expressions into Integrated Circuits". NASA Sti/Recon Technical Report N. 81. Fairfax County, Virginia: Ft. Belvoir: Defense Technical Information Center: 12334. Bibcode:1980STIN...8112334F.

@hipsterelectron@circumstances.run 2 hr. ago

also i did spend a good deal of time trying to find an actual living example of euclid's elements and all i could find was some fucking cambridge asshole saying outright that he had written every part of it himself. and of course it all acted like "formalism" was such a huge fucking important thing back in ancient fucking greco-mathematics

@hipsterelectron@circumstances.run 2 hr. ago

ok so bisecting an angle with a compass and straightedge is a pretty direct corollary of the even numbers being a ring closed under multiplication and addition? yes? ok great. now what else

@hipsterelectron@circumstances.run 2 hr. ago

ok so angle bisection corresponds to the ring operation. there's also a very clear higher-dimensional analogy for pythagorean triples and it's just the same thing as the "euclidean" norm?????

@hipsterelectron@circumstances.run 54 min. ago

i'm reading about the monster group now https://sci-hub.st/10.1038/scientificamerican0680-20 afaict it's another little fairytale the princeton mathematicians are telling themselves

@hipsterelectron@circumstances.run 53 min. ago

"oooooooo once we factor the monster group we specifically made up in our heads to sound scary we're gonna crack all your isomorphisms or whatever now ooooo"

@hipsterelectron@circumstances.run 51 min. ago

i can tell you right now i really will need help to avoid trying to prove P < NP based upon modular exponentiation and euclid's least common multiple methodology. it's so incredibly fucking obvious that's the truth now

@hipsterelectron@circumstances.run 33 min. ago

to be clear, i absolutely have not figured it out yet. to me it's quite clear there are two flaws that have stalled progress:

gauss just asserted uniqueness of prime factorization despite multiplication of integers being an inherently commutative operation. he then decided 1 doesn't count. that's the single thing we need!!! yes 1 divides everything arbitrarily often!!!! euclid didn't have a problem with that!!!
i don't think goldbach's conjecture is true (or at least i don't care). the even integers already have this beautiful ring structure!!!! stop fucking up my beautiful numbers doing their job perfectly!!!!
the primes without 1 and 2 are their own little thing! they all start from one spot then have these cute little directed edges into composites. but each multiplication operation forms a hypergraph edge.

and i think to model it correctly we need a distinct hypergraph edge for every distinct combination of 3+ prime factors to their products. so an edge for 32 => 9, but a separate edge for 33 => 27. we can calculate transitivity later, i just want to model this!

then add infinite edges from 22 => 4, 23 => 8, etc, and keep those edges separate. then add a copy of every 3+ compositional edge for each of the infinite powers of 2 added as a new factor.
then add a loop edge 1 => 1, then 1 x n => n forall n

@hipsterelectron@circumstances.run 28 min. ago

so we have our hypergraph from hell almost ready to go, but we should make two more operations:

add 1, then take to a power of 2
take to a power of 2, then add 1

but i think that sucks actually though. the point is we need to help get all the 1 divisors who've been trapped in their own ideal for centuries to help us with our little CSPRNG system

Log in