mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-03-11, 13:21   #1
Peter Nelson
 
Peter Nelson's Avatar
 
Oct 2004

232 Posts
Default Applications of factoring

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?
Peter Nelson is offline   Reply With Quote
Old 2007-03-11, 19:52   #2
sean
 
sean's Avatar
 
Aug 2004
New Zealand

111000112 Posts
Default

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.
sean is offline   Reply With Quote
Old 2007-03-13, 01:10   #3
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

48516 Posts
Default

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.
geoff is offline   Reply With Quote
Old 2007-03-13, 21:32   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2C1F16 Posts
Default

Quote:
Originally Posted by Peter Nelson View Post
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
xilman is offline   Reply With Quote
Old 2007-03-13, 21:58   #5
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

484410 Posts
Default

Quote:
Originally Posted by xilman View Post
Yes.

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


Paul
Not in Italy...

Luigi
ET_ is offline   Reply With Quote
Old 2007-03-14, 12:14   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by ET_ View Post
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)
R.D. Silverman is offline   Reply With Quote
Old 2007-03-15, 19:32   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Repรบblica de California

32·1,303 Posts
Default

Quote:
Originally Posted by xilman View Post
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."

Last fiddled with by ewmayer on 2007-03-15 at 19:33
ewmayer is offline   Reply With Quote
Old 2007-03-15, 19:54   #8
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24×33 Posts
Default

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
m_f_h is offline   Reply With Quote
Old 2007-03-16, 05:41   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

5·709 Posts
Default

Quote:
Originally Posted by xilman View Post
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
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Wired digital cock has appeared on certain Windows applications kladner Information & Answers 20 2015-01-22 19:24
Microsoft, ignoring the irony, files 10 software patent applications per day ewmayer Lounge 0 2005-07-31 19:42
AMD64 Applications with Visual Studio 6 or .Net Ethan (EO) Software 0 2004-08-09 04:07

All times are UTC. The time now is 23:42.


Fri May 20 23:42:11 UTC 2022 up 36 days, 21:43, 0 users, load averages: 0.97, 1.27, 1.36

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”