User Controls
Factoring: how hard could it be?
-
2023-03-24 at 6:47 PM UTCMaking thread related to factoring and other interesting computational problems.
Previous posts
Originally posted by Sweet Bruh how do we beat the General Number Field Sieve for factoring large semiprimes?
Originally posted by Sweet Factoring large semiprimes. How can it be so hard?
Originally posted by Sweet Fermat's difference of squares method and area method are really good for small semiprimes but for larger semiprimes you gotta search for the right difference of squares or the right Pythagorean triple so it still remains a search problem.
That's fucking retarded, I feel like there should exist some simple functions you can plug an semiprime integer into to get the x and y factors. Or like a system of equations.
Originally posted by Sweet Complaining to God about why he decided to make mathematics some certain way.
Originally posted by Sweet They literally already did that, I'm part of that internet going "we'll see about that stoopid"
https://en.m.wikipedia.org/wiki/RSA_Factoring_Challenge
Originally posted by Sweet Currently the most advanced factoring algorithm is known as General Number Field Sieve and it's an extremely sophisticated algorithm that leverages several advanced concepts from number theory and linear algebra to factor large semiprimes.
The thing is. The second you have to start "guessing" or "searching" anything, shit gets horrible for large semiprimes. Lots of methods work for small semiprimes but if any step involves a search or guess, it's almost guaranteed it won't scale well to a large semiprime.
So I am really hoping there's some more direct way to just manipulate the integer. That would essentially "crack" factoring in full. But of course that's probably pretty hard and it's likely some simple algorithm or set of functions like I wanted doesn't exist.
Originally posted by Sweet Imagine you have a big problem and you throw all your smartest guys at it and the best answer they have is just "yeah this one is fuckin tough chief"
Originally posted by Sweet I am reading about something callef holographically reduced representations. They have some semi-miraculous mathematics behind them that allow you to solve some pretty "hard" properties of graphs in polynomial time, specifically Perfect Match.
I think you can use an advanced version of Dijkstra's algorithm on them to solve some very hard computational problems but it hasn't been well explored as an algorithmic technique yet. Holographic algorithms in general have not been well explored yet.
I'm not exactly sure what they could have to do with speeding up factoring yet but I feel like an "expansion" of a semiprime integer is required rather than a reduction of any search component of existing factoring algorithms.
But I'm not ruling out that possibility either.
I have a weird feeling like you can do the Area Method without needing to just search for Pythagorean triples. That's where the scaling goes to shit in Area Method, Fermat Method (search for difference of squares) etc at large integer lengths.
Originally posted by Sweet It's like, there is only one rectangle of integer side lengths that can have semiprime area. I feel like that's some kinda clue. There are a bunch of other geometric relations you can put the semiprime into the middle of. They all kinda evade giving you the unique length though. That might be a hint at the problem being fundamentally hard but that just seems so "accidental", no? So really there's not even so e relation in any number of dimensions where even by accident you can plug in the integer to 2 sets of manipulations and output 2 numbers that correspond to the 2 factors, for reasons that are otherwise totally unrelated to "solving factoring"? I mean you can write a function to make any integer output any other shit.
Originally posted by Sweet Tbh I honestly don't care about cryptography so much as I care about the basic math itself tbh. It just seems so arbitrary and stupid that factoring semiprimes should be so hard.
I think lots of amateurs dicking around with basic algebra and geometry and shit is useful. I think there is still a lot of juice left even in basic euclidian math because simply put we have never before din history had the sheer volume of math literate human beings walking around the Earth to the level we have now. E.g. Every guy who knows basic algebra would be one of the smartest people walking around ancient Greece.
There is the "infinity monkeys on infinity typewriters" principle but if you go from monkeys to humans and typewriters to the right basic tools, you can start putting more reasonable and useful bounds on what kind of realistic outcomes you can get and tbh maths is one of those things where the basic stuff we're taught is adjacent to an absolute monstrous amount of silent basic dependent logical structures that nobody ever really talks about or feels the need to explore.
Who knows what kind of interesting stuff is yet to be hit upon?
Originally posted by Sweet Their "waist" is always the square formed by the square root of the prime, but that's not always on the aforementioned "slice map". It seems useful to always map the square root anyway.
Originally posted by Sweet Semiprimes only have 3 rectangles with whole integer lengths, Nx1, 1xN and then the prime factors. Shit starts getting wild when you start mapping various non integer rectangles but I feel like there is some kind of hint there.
Originally posted by Sweet I feel like there should be some smooth transition factor you can calculate there between 1xN, Nx1, the Square Root and the Prime Factors
-
2023-03-24 at 7:03 PM UTC
Originally posted by Haxxor When the prime factors of a semiprime are large, factoring it becomes a computationally difficult problem, even for modern computers. This forms the basis for the security of many modern cryptographic systems, such as RSA encryption.
The difficulty of factoring large semiprimes is due to the lack of efficient algorithms for factoring. However, there are some techniques that can be used to factor large semiprimes, such as the Number Field Sieve (NFS) algorithm and the General Number Field Sieve (GNFS) algorithm. These algorithms are complex and require significant computational resources.
In general, the larger the semiprime, the more difficult it is to factor. This is why cryptographic systems that use large semiprimes for encryption, such as RSA, are considered secure as long as the semiprimes used are sufficiently large. -
2023-03-24 at 7:45 PM UTCHave you tried using AI
-
2023-03-24 at 8:16 PM UTCYeah I feel like there's just gotta be some simple enough functions where you plug in the semiprime integers and do a very simple set of operations like multiplications, and spit out the factors. Not even for the reason of specifically solving factoring, just as a random mathematical structure, just so happens to spit out something darn close to the right factors. Like any good approximation algorithm.
-
2023-03-24 at 8:48 PM UTCsounds like something that would best be coded in
-
2023-03-24 at 9:39 PM UTC
-
2023-03-25 at 3:05 AM UTCAI is fake and gay
I mentioned Project Euler before, might give it a try again if anyone else is interested in working through it
https://projecteuler.net
basically a list of math problems that require programming to solve them, each progressively more difficult, not necessarily with a focus on primes and cryptography but some of them are related -
2023-03-25 at 3:21 AM UTC
