30 ms·

Prime Factorization - Just as a fun side project. I do not expect that I will ever be able to solve it but at least once a week I learn something new about math

Prime Factorization - Just as a fun side project. I do not expect that I will ever be able to solve it but at least once a week I learn something new about math! I've Been working on it for 3 years now and It's getting more and more fun every day. In fact, I have rediscovered so many things on my own that I thought never existed. My biggest "Eureka" moment was when I discovered factorization via the difference of squares method on my own by using 2D geometry. I previously did not know that such a method existed nor that GNFS is based on it. Later on I discovered that a composite number is actually a perfect square less a function of a triangular number which lead me to develop a method of factorization that is rather cool but unfortunately still not good enough. I have had literally dozens of these moments where I find a certain relationship between numbers that I later on find out is some sort of rule/conjecture that was made hundreds of years ago by some mathematician! To some of you these might be really trivial and well known facts that you learned in school. For me however, it is something I take pride in as math was by far my worst subject growing up and I actually dropped out of college because of math. The last math course I took was in high school over 10 years ago. I have a new found love for mathematics and algebra in general and I would encourage anyone reading this to pick a problem and try working on it just for the fun of it :D

Ono-Sendai 10y ago
What exactly is the problem? Finding the prime factors of numbers? Or doing it fast?
- demonshalo 10y ago
  basically doing it fast for large integers. Here is the challenge I am working toward: https://en.wikipedia.org/wiki/RSA_Factoring_Challenge https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
  - Ono-Sendai 10y ago
    Ok cool. I'm a big fan of taking on fundamental problems like this. Even if you're unlikely to get anywhere, you always learn a lot :) Nice that there's a cash price for incentive as well.
  - 1001101 10y ago
    If you have a breakthrough and start factoring RSA numbers and >=1000 bit composites (edit: on a system that costs less than 100 billion $), I would definitely start thinking about OpSec and finding a nice signal free place to crash. Good luck :)
    - demonshalo 10y ago
      lol. Like I said, I don't expect to reach any tangible goal. However, I am not looking for an extended "search" algorithm. I am looking for a "solution" or at least a solution in say O(log(n)) to begin with. That's the goal I put up as a challenge. I will most likely not be able to do that but still fun to try :D Edit: Forgot to say thanks!
  - tmescic 10y ago
    IBM has these monthly challenges called Ponder This, and this month's challenge is to factor 3 large numbers (~100 decimal digits). Have a look: https://www.research.ibm.com/haifa/ponderthis/challenges/April2017.html https://www.research.ibm.com/haifa/ponderthis/challenges/Apr...
    - demonshalo 10y ago
      sweet! I didn't know about this. Thanks for the link.
andai 10y ago
I have had a hard time with math in formal education, I would love to hear more about how you are learning it now :)
- demonshalo 10y ago
  I know that feeling! I just took on a problem that I found to be simple to understand yet for some reason is still unsolved. Simple to understand turned out to be crucial because when I started I had no idea how much "I did not know" and for that reason I underestimated the problem which is a GOOD thing. It allowed me to slowly grow with the problem over time and learn more about what I need to do to get to where I want to. The most important part for me is to find a problem that is interesting enough that will keep sucking you back in. Prime factorization is a great example because it is a simple problem so you will continuously make progress and actually feel/see your personal math improvement from week to week. Initially, I started off by writing down all the numbers up to N to see if I could find some pattern. 20 mins in after some HTML and PHP I had this: https://imgur.com/a/7EhdI https://imgur.com/a/7EhdI (primes in blue, everything else in white) If you look closely you can see the diagonal shape of the primes. If you try changing the number of columns from 5 to any other number, you will get a distinct shape. The shapes sucked me in, why do they occur? wtf is up with them?! this is so cool yet random. After having my curiosity tickled, I opened up an excel sheet and started experimenting by throwing these numbers/positions/order/whateverICanThinkOf together in an attempt to find some pattern. Currently, I have an excel file that consists of 35 sheets with different experiments on each sheet. Most experiments and ideas will fail, some will give you a result. But one thing is for sure, I have learned something from each one of them, especially when it comes to algebra. I just get an idea and try it. If I need some help I ask around or google for some info. The latest idea/experiment that I did showed me that composite numbers do not occur in a random position along the axis of numbers. In fact, numbers come in chains that are related to each other "geometrically". That's it really. It's like throwing whatever you can think of at a problem to see what sticks. While attempting to do that I slowly learned algebra, a bit of genometry, a bit of statistics and then some. Been fun really and that's all that counts :D edit: sorry for the wall of text!
gavanwoolery 10y ago
I used to spend a good deal of my time looking for patterns in prime numbers - and similarly re-discovered many older theorems. It is an addictive activity for certain :)
- demonshalo 10y ago
  Indeed it is :D

Ono-Sendai 10y ago

What exactly is the problem? Finding the prime factors of numbers? Or doing it fast?

demonshalo 10y ago
basically doing it fast for large integers. Here is the challenge I am working toward: https://en.wikipedia.org/wiki/RSA_Factoring_Challenge https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
- Ono-Sendai 10y ago
  Ok cool. I'm a big fan of taking on fundamental problems like this. Even if you're unlikely to get anywhere, you always learn a lot :) Nice that there's a cash price for incentive as well.
- 1001101 10y ago
  If you have a breakthrough and start factoring RSA numbers and >=1000 bit composites (edit: on a system that costs less than 100 billion $), I would definitely start thinking about OpSec and finding a nice signal free place to crash. Good luck :)
  - demonshalo 10y ago
    lol. Like I said, I don't expect to reach any tangible goal. However, I am not looking for an extended "search" algorithm. I am looking for a "solution" or at least a solution in say O(log(n)) to begin with. That's the goal I put up as a challenge. I will most likely not be able to do that but still fun to try :D Edit: Forgot to say thanks!
- tmescic 10y ago
  IBM has these monthly challenges called Ponder This, and this month's challenge is to factor 3 large numbers (~100 decimal digits). Have a look: https://www.research.ibm.com/haifa/ponderthis/challenges/April2017.html https://www.research.ibm.com/haifa/ponderthis/challenges/Apr...
  - demonshalo 10y ago
    sweet! I didn't know about this. Thanks for the link.

andai 10y ago

I have had a hard time with math in formal education, I would love to hear more about how you are learning it now :)

demonshalo 10y ago
I know that feeling! I just took on a problem that I found to be simple to understand yet for some reason is still unsolved. Simple to understand turned out to be crucial because when I started I had no idea how much "I did not know" and for that reason I underestimated the problem which is a GOOD thing. It allowed me to slowly grow with the problem over time and learn more about what I need to do to get to where I want to. The most important part for me is to find a problem that is interesting enough that will keep sucking you back in. Prime factorization is a great example because it is a simple problem so you will continuously make progress and actually feel/see your personal math improvement from week to week. Initially, I started off by writing down all the numbers up to N to see if I could find some pattern. 20 mins in after some HTML and PHP I had this: https://imgur.com/a/7EhdI https://imgur.com/a/7EhdI (primes in blue, everything else in white) If you look closely you can see the diagonal shape of the primes. If you try changing the number of columns from 5 to any other number, you will get a distinct shape. The shapes sucked me in, why do they occur? wtf is up with them?! this is so cool yet random. After having my curiosity tickled, I opened up an excel sheet and started experimenting by throwing these numbers/positions/order/whateverICanThinkOf together in an attempt to find some pattern. Currently, I have an excel file that consists of 35 sheets with different experiments on each sheet. Most experiments and ideas will fail, some will give you a result. But one thing is for sure, I have learned something from each one of them, especially when it comes to algebra. I just get an idea and try it. If I need some help I ask around or google for some info. The latest idea/experiment that I did showed me that composite numbers do not occur in a random position along the axis of numbers. In fact, numbers come in chains that are related to each other "geometrically". That's it really. It's like throwing whatever you can think of at a problem to see what sticks. While attempting to do that I slowly learned algebra, a bit of genometry, a bit of statistics and then some. Been fun really and that's all that counts :D edit: sorry for the wall of text!

gavanwoolery 10y ago

I used to spend a good deal of my time looking for patterns in prime numbers - and similarly re-discovered many older theorems. It is an addictive activity for certain :)

demonshalo 10y ago
Indeed it is :D