Applications of factoring

[Peter Nelson]

One of the reasons people would like to be able to factor large products of 2 primes is to break the encryption techniques currently popular for e-commerce etc.

The guy from m-wave systems argued that "factoring" is not the killer app for quantum computing. His reasoning was that once current encryption was broken, people would just move to a new encryption algorithm which was not easily solvable using quantum techniques.

Of course if messages now were archived, they could be decrypted retrospectively which might still reveal valuable information.

He seemed to be dismissing factoring as an app for quantum hardware.

That set me thinking:

I know that being able to factor is actually useful to us here in searching for primes ie eliminating candidates in early stages. If a quantum computer could help us do that it would be irrelevant that contemporary encryption was obsolete.

So, my question to the forum is:

Can factoring of itself actually be useful for other things?

[sean]

Factoring is used in more than one way in primality proving. You seem to be aware that is used to eliminate candidates for primality testing, but it is also used in the construction of some forms of primality proof. For example, if you have have putative prime p, then factoring circa 30% of p-1 and/or p+1 is enough to generate a proof of primality.

There is also a project discussed elsewhere in this forum where factoring is used to help establish bounds for the existence (if any) of an odd perfect number.

[geoff]

Studying the structure of composite integers has been of interest for thousands of years, and will be of interest for thousands more. It is just a coincidence that for a few decades it was useful too.

[xilman]

Originally Posted by Peter Nelson

So, my question to the forum is:

Can factoring of itself actually be useful for other things?

Yes.

It can lead, directly or indirectly, to offers of paid employment.


Paul

[ET_]

Originally Posted by xilman

Yes.

It can lead, directly or indirectly, to offers of paid employment.


Paul

Not in Italy...

Luigi

[R.D. Silverman]

Originally Posted by ET_

Not in Italy...

Luigi

Nor in the U.S.

As to the original question about applications of factoring other than
breaking RSA:

There aren't any, other than in pure mathematics (e.g. finding the structure of
finite fields)

[ewmayer]

Originally Posted by xilman

It can lead, directly or indirectly, to offers of paid employment.

Interesting personal note about that aspect, although (for the technicsl quibblers) in my case it was really primality testing (specifically, fast algorithms for):

When I moved to Silicon Valley in 1999, given the local job market, nobody around here cared one whit about the area I'd done my University work in, namely Theoretical and Computational Fluid Mechanics. But when I had my first few interviews with (typically quite skeptical, given my background) recuiters for local tech companies, I found when I mentioned my prime-testing coding work (which had begun as a sidelight, an interesting application of FFTs to help my engineering students understand applications of transforms), their eyes invariably lit up - big-time tech-nerd cool factor there. These days of course I have enough actual silicon-related work to put on my CV that I no longer need to worry about my qualifications being of interest to Silicon Valley employers, but am proud to say that my primes-related work, modest as it has been, was key to getting me that first "In."

[m_f_h]

In some sense, factoring is more productive than primality testing... (the latter just produces a single bit of information)...

I apologize for a somewhat ill-placed question : (which will again reveal my ignorance on the subject...)
The file lowm.txt seems to give complete factorizations of Mersennes
Mq for q=2^k from q=16384 up to q=67108864
plus smaller values of qn from 787 to 9973 (looks as if this were (all(?)) primes between 787 and 1e4)
Is there some explanation available ? why "small" primes > 787 and < 9973 and "big" powers of 2 ?


PS: a google search for "lowm-txt lowp-txt files contain factors of Mersenne numbers" gives only 6 pages on which I did not find the info on my question

[jasonp]

Originally Posted by xilman

Yes.

It can lead, directly or indirectly, to offers of paid employment.


Paul

I have to agree with Paul and Ernst here. I would have no qualms about putting msieve on a resume; as code samples go, it's a doozy. I know for a fact that someone at my current job was specifically impressed at interview time that I would do stuff like this for fun.

jasonp