I've had this idea since 2009: converting the integer factorization problem into a visual geometric constraint puzzle (based on Lattice/Gelosia multiplication). The idea is to see if we can spot symmetry-breaking patterns in the 'carry' bits, or constraints on the remainders/quotients over some radix based on divisibility implications of already selected units in the tableaux. In other words, the kind of domain-specific things that "domain-blind" SAT solvers miss.
There's a variety of constraints included, but there could be a lot more. My feeling has always been it's going to be possible to find a set of constraints that "breaks the symmetry" and lets you factor these kind of integers quickly. I have a hunch it involves "diffing across radices", in other words, get k_i bits of entropy by making some choices in radix r_i, move to radix r_i', translate those contraints into that, make some more choices, get a few more bits of entropy there, and just keep going.
Also various ways of propagating constraints through the tableaux (forward and back propagation, arc and path consistency, etc). This puzzle implements just a few of those things.
So, for now it's not about "bringing down the global financial system" (don't worry "RSA" is "safe for now" ;D) but just somethng fun to play with to give you a feel for the puzzle. If it gives you some instincts about the inner workings of the factoring puzzle, I feel happy.
This little demo definitely could improve a lot more! Enjoy :)
gus_massa•2mo ago
Sorry, but no idea what I should do. Even after pressing "Reveal all". Are there a few 3 digits number hidden somewhere?
Anyway, "Auto-Prop" should be closer to the checkbox.
keepamovin•2mo ago
Right...good point! Okay so the two arches at the top are the factors' digits. The horizontal bar down the bottom is the product (semiprime) digits. And the diamond is the "multiplication tableaux" (each cell is the produce of some pair of factor digits, split into two halves, a quotient and remainder modulo the radix). The vertical columsn of this diamond (highlighted visually when you hover over a product digit) sum (with carry) to give the corresponding product digit.
So the idea is you make guesses on the values in the cells (in the arches or the tableaux) and these guesses have consequences (some of which are "auto propagated" and displayed visually).
The goal is you use these intersecting contraints to deduce the digits of the prime factors thus solving the factorization of the semiprime.
That help?
gus_massa•2mo ago
It helps a lot. You should add a question mark that shows some explanation, and perhaps an example. Some random ideas:
Here in Argentina we put the intermediate numbers in horizontal lines, so it's hard to guess what is happening. With the explanation and some tries I got the idea.
Perhaps repeat at the bottom [p2][p1][p0]x[q2][q1][q0]=number, replacing p... and q... with the selected numbers
It would be nice that the correct digits in the result number at the bottom are painted green and the wrong red.
I want confetti when I win!!! :)
Auto-prop is too strong and ruins most of the fun. But perhaps it's too hard without auto-prop.
The only strategy I found if to use guessing a.k.a brute force.
Important: When a slot has zero options, it should show "0" instead of "<= 10".
Important: When a number is selected and I want to change it, let's say 7 to 3, it should be possible to do this in a single step. Now it needs two steps: "7 -> clear" and "clear -> 3". The idea is that when I click on the seven, the pop up window should show the 7 in one color and all the other valid options in other like 2, 3, 9. So I can click directly on the 3.
keepamovin•2mo ago
Thank you, gus. These are good ideas! I will try a default to auto-prop off.
For the rest I will think more and consider ways to bring them. Appreciated! :)
keepamovin•2mo ago
There's a variety of constraints included, but there could be a lot more. My feeling has always been it's going to be possible to find a set of constraints that "breaks the symmetry" and lets you factor these kind of integers quickly. I have a hunch it involves "diffing across radices", in other words, get k_i bits of entropy by making some choices in radix r_i, move to radix r_i', translate those contraints into that, make some more choices, get a few more bits of entropy there, and just keep going.
Also various ways of propagating constraints through the tableaux (forward and back propagation, arc and path consistency, etc). This puzzle implements just a few of those things.
So, for now it's not about "bringing down the global financial system" (don't worry "RSA" is "safe for now" ;D) but just somethng fun to play with to give you a feel for the puzzle. If it gives you some instincts about the inner workings of the factoring puzzle, I feel happy.
This little demo definitely could improve a lot more! Enjoy :)
gus_massa•2mo ago
Anyway, "Auto-Prop" should be closer to the checkbox.
keepamovin•2mo ago
So the idea is you make guesses on the values in the cells (in the arches or the tableaux) and these guesses have consequences (some of which are "auto propagated" and displayed visually).
The goal is you use these intersecting contraints to deduce the digits of the prime factors thus solving the factorization of the semiprime.
That help?
gus_massa•2mo ago
Here in Argentina we put the intermediate numbers in horizontal lines, so it's hard to guess what is happening. With the explanation and some tries I got the idea.
Perhaps repeat at the bottom [p2][p1][p0]x[q2][q1][q0]=number, replacing p... and q... with the selected numbers
It would be nice that the correct digits in the result number at the bottom are painted green and the wrong red.
I want confetti when I win!!! :)
Auto-prop is too strong and ruins most of the fun. But perhaps it's too hard without auto-prop.
The only strategy I found if to use guessing a.k.a brute force.
Important: When a slot has zero options, it should show "0" instead of "<= 10".
Important: When a number is selected and I want to change it, let's say 7 to 3, it should be possible to do this in a single step. Now it needs two steps: "7 -> clear" and "clear -> 3". The idea is that when I click on the seven, the pop up window should show the 7 in one color and all the other valid options in other like 2, 3, 9. So I can click directly on the 3.
keepamovin•2mo ago
For the rest I will think more and consider ways to bring them. Appreciated! :)