0%
0%

Factoring using waveforms

Waveform sweep superposition to help factor large product of prime numbers.

Similar projects worth following
327 views
NOTE: This is a total shot in the dark and is only here to check and see if the approach is even valid. Chances are it's off the mark. But, nothing ventured, nothing gained.

The idea is as follows:
For any given number N which is a product of two primes A and B
Convert N to a frequency in Hertz
Create a frequency sweep from 1htz to N over a period of time
Combine the two samples

Because only 1, A, B, and N frequencies will be factors of N, the combined samples should create patterns similar to the 'beats' that appear when tuning an instrument.

In my case, due to limitations, I was testing this in audacity. I used 16351 hertz; the product of 83 and 197. Strangely enough, upon viewing the spectrograph (as uploaded) a few sets of clear horizontal lines composed of dots appeared. The bottom one appears to be around 83 hertz and fades as frequency raises, the next one up appears around the 197 mark (more or less)

My goal here is to test out some interesting concepts and learn a few things along the way. I have no illusions that this will be ground breaking, but it could be pretty cool, possibly even a novel curiosity.

Previously, I was only looking to find someone more skilled to test this, at this point though, I've learned enough that I can start to test things on my own.

• Maybe not as naive as I thought but still incomplete

So, without mincing words, the approach I originally proposed is certainly incomplete, however I was unknowingly  stumbling into some interesting concepts.

Here's the core of what I found out through this:

All factors of numbers are harmonic with the composites made of them.
When graphed in XY mode on an Oscilloscope, a number and its harmonics will not rotate, regardless of relative phase between them
Wave-wise, This rotation is also akin to the beats one would hear if two notes were out of tune

What I was working with was part of the baby steps needed to understand shor's algorithm.  The core concept that all numbers can be represented as frequencies, constructive and destructive interference, as well as other important things.

Something that I learned later:

Shor's algorithm operates based on periodicity.  For a given semi-prime, If we take the length of the periodic cycle of ((2^X)mod N), where x is the step number, we can learn about the P and Q that N is made of (assuming N is an integer not divisible by 2).  Specifically, (P-1)*(Q-1) = the length of the periodic cycle of ((2^X)mod N) * an integer.

To put it another way, if the length of that periodic cycle is known as W, we can say ((P-1)*(Q-1))mod w = 0.  Which is really pretty cool seeing as right there we now know that any given factor of N has to fit this pattern and has to be between 3 and N/3.  Factoring the number becomes more like tuning a guitar than doing hard math.

It doesn't sound like much, but by using some cool tricks with phase analysis on a quantum machine (assuming there's one capable of doing so), we can actually get results.  Without a quantum machine, you can (and I did) actually even use this information to factor things on paper.  Note: for doing it on paper, unless you hate your life, don't go above 4 digit semi-primes.  Even a 4 digit semi required the use of wolfram as my tiny calculator did not appreciate trying to modulus through a periodic sequence of 48.

• Results

At this point, I'm fairly sure this approach is naive. There is a merit in the realm of analyzing periodicity and in the fact that audacity, from my understanding, works on the basis of a FFT of the wave itself. But as stated before, a shot in the dark was all it was, it was a miss, but hey, it was an interesting thought. When I learn more about signal analysis I might take another look at this concept, but until then, I'll put a fork in this one.

• Added a few reference papers

EDIT2: Tomorrow is a very long time away sometimes. Spoke to a higher up professor in physics, specifically, one whom specializes in acoustics and waveform analysis and while we can see that I was getting results, by all means, I shouldn't be. So the next step is to refine the test to better account for error. The new wave output will be generated via mathmatica and the analysis done by Raven, a software from Cornell. The next step after that will be dependent on what the new results are. If they are in fact error caused by poor fidelity, then I'd like to try frequency modulation and a few other things. Moreover, if it is an error, but it still gets accurate results, then it would be worth looking into what can be done to replicate that error to turn it into an intended feature.

Past that, it's been a matter of learning more, increasingly difficult maths. Chipping away at pdf after pdf in order to understand concepts. The newest document I'm reading over has a strikingly similar concept behind it. It essentially boils down to the fact that division is a very costly operation and by performing said division on a physical system (for example, a wave) it could speed up computation time, even for something like factorization.

Anyways, back to studies

=================
EDIT: Got distracted by video games so it will wait until the morning
=================
I had a really nicely worded post and firefox decided to crash. I plan to rewrite it again in the next few minutes, but until then, here's a placeholder to remind me of content included until I edit this post back to its former state.

Spending a few hours a day researching
Lots of crazy subject matter intersecting
Post some equations I figured out

• Progress

Been testing a few things out and found some materials that seem to suggest that I may be on the right line of thought. Grabbing one of the physics professors at my university to see if he can give me advice and either confirm or deny that what I'm suggesting is in fact possible.

To restate, Unlike most approaches to factoring, my goal is not to get exact numbers but instead to use the frequency sweep to quickly narrow down the number of possible factors from N to a much smaller fraction of N which can then be computed via standard means. Like tuning the top string of a guitar by playing the bottom string and listening to the wobbles (almost exactly actually).

http://arxiv.org/pdf/quant-ph/0503228v1.pdf

This link is one of the papers I've been looking through that seems to confirm my general thoughts on the matter, but I intend to get a more educated opinion before I commit to this as my graduation project.

Emails will be sent out today, meeting with the profs should occur in a week or so depending on how busy they are.

Share

Discussions

Mark Sherman wrote 11/18/2016 at 21:49 point

I don't know if only integer factors of the frequency will show up.  Suppose you try to factor 55 Hz.  Would you only see 5Hz and 11Hz?  Why won't you see 4Hz and 13.75 Hz?  Hz is based on the second, which is an arbitrary unit of time humans just made up.  There is an infinite number of ways to make 55 hz.

Are you sure? yes | no

Wudagem wrote 09/22/2016 at 14:01 point

I think your answer depends on your goals. I can't speak to whether your idea would work in theory (seems likely), but from a practical side I don't think it's useful. If you want to know in theory if it will work I'd continue talking to researchers.

For example, slapping "factor (2^100 + 17)" into wolframalpha.com returns a near instant prime factorization of it, converting that into a frequency as described would require an analog system capable of working at gamma ray frequencies. A desktop computer is fairly capable of factoring numbers significantly larger than that without too much time expended, factoring numbers like 1877138824359859508015524119652506869600959721781289179190693027302028679377371001561 (~2^280) require only about a minute with modern algorithms and a desktop computer.

If you could refine the strategy to only require frequencies in the range of log(N) then it could be interesting, but I have a suspicion that (if possible) all that would do it trade off high frequency requirements for very high accuracy requirements, which would also be very difficult to build.

Are you sure? yes | no

Macrofarad wrote 09/30/2016 at 04:59 point

For sure, realistically, I'm very aware that what I'm doing won't be game breaking. I'm just one guy (an undergraduate no less) who had an inkling that he wanted to try something interesting. To refine these concepts into something actually useful would likely take years and math that, for now, is a bit above my skill level. To me, this is just an excuse to push my skills higher and have some fun learning. (And yes, I'm still grabbing as many knowledgeable people as I can to help guide my studies on this)

As it stands currently, I have found many more papers relevant to the subject and have been working at deciphering (and posting) them.  Currently, the most relevant one I've found is this: https://arxiv.org/pdf/1505.04577v1.pdf which is listed under links now (analogue algor...).

To address your feedback directly, I agree that frequency/accuracy may end up being a limiter but the good news is that light gives me a surprising amount of wiggle room if other mediums don't pan out.  Moreover, while I'm still working at understanding what would need to be done to perform it, a few of the papers I've read through mentioned being able to scale similar algorithms due to them being based on physical properties.

Bit of a lengthy reply but I hope I covered everything.  Regardless, thank you for the feedback, helps keep me on target

Are you sure? yes | no

nats.fr wrote 07/20/2016 at 12:47 point

Hello,

Any chances it's related to FFT used as a fast multiplication ?

http://numbers.computation.free.fr/Constants/Algorithms/fft.html

Are you sure? yes | no

Macrofarad wrote 07/22/2016 at 13:27 point

I'll be frank here, offhand I have no idea, but it's worth looking into.

At the time of figuring this out, I was playing with a quantum simulator pretty frequently (http://algorithmicassertions.com/quirk). More specifically, I got the idea when finding out about Shor's algorithm which actually uses QFT.  Looking at it now, if I'm understanding right, Shor's is doing stuff with phase to find if a number is a factor.  If that is the case, than my experiment as it turns out, isn't that different. So, possibly?  I'm still learning the math at this point so that's about the best answer I can give you currently.

Are you sure? yes | no

Does this project spark your interest?

Become a member to follow this project and never miss any updates