Talk:Integer factorization

This article is rated B-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics High‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics High This article has been rated as High-priority on the project's priority scale. Cryptography: Computer science Mid‑importance This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography Mid This article has been rated as Mid-importance on the importance scale. This article is supported by WikiProject Computer science (assessed as Mid-importance).

Archives

1

This page has archives. Topics inactive for 365 days are automatically archived 1 or more at a time by Lowercase sigmabot III if there are more than 10.

(I also posted something similar to this at Talk:Fundamental theorem of arithmetic.) Several sources I've seen only state the Fundamental Theorem of Arithmetic for integers strictly greater than 1. Of course, I understand the argument about 1 being an empty product of primes, and I do admit that this convention makes the statement of the Fundamental Theorem of Arithmetic a lot cleaner. Nevertheless, I think it's worthwhile at least to mention that there are two prevalent conventions. We can do that here, or we can refer readers to the Fundamental theorem of arithmetic article if the change I propose is made there. I don't mind making the changes myself, but I wanted some kind of discussion first. For some odd reason, these small trivialities produce huge controversy and I don't want to step on anyone's toes. VectorPosse 06:36, 3 March 2007 (UTC)[reply]

Frankly, that seems out of context here - better to avoid mentioning it if possible and discuss the two conventions briefly at fundamental theorem of arithmetic and/or multiplication. Make sure to link the article empty product. Dcoetzee 22:03, 24 July 2007 (UTC)[reply]

I agree that the question of the proper statement of the theorem is an unnecessary distraction in this context. I've shortened what was there by simply stating it for all positive integers along with a parenthetical remark about the empty product convention. Vaughan Pratt (talk) 22:02, 19 March 2016 (UTC)[reply]

It is relatively trivial to re-arrange the well-known (x+y)(x-y) formula to demonstrate that for any odd whole number 'a', there are two perfect squares 'b' and 'c' such that a + b = c. Further, if you know 'b' and 'c', from these you can work out two factors of 'a' from the same formula (if 'a' is prime, obviously the two factors would be the number one and the number 'a' itself)

Are there any factorization algorithms which exploit this fact, and look for 'b' and 'c' to work out the factors indirectly?

I've looked down the list of methods here, but couldn't see anything obvious, though some of the maths goes over my head!

CG 80.229.220.254 (talk) 20:42, 25 May 2012 (UTC)[reply]

Fermat's factorization method may be the simplest method exploiting this idea. Continued fraction factorization, the quadratic sieve and the number field sieve are more advanced algorithms that also try to represent n or a multiple of n as the difference of two squares. 178.195.225.28 (talk) 11:06, 26 May 2012 (UTC)[reply]

In short, it is very unlikely (i.e. impossible in practice) that the integer you wish to factorize can be represented as the difference of two squares. I doubt the attack is efficient anyway, but I don't have a convincing argument handy. Skippydo (talk) 14:08, 26 May 2012 (UTC)[reply]

The Fermat basic method consists of subtracting "a" from various integer squares "c" until you find one where the remainder, "b" is a square. However, is there a documented variation where you keep adding various integer squares "b" to "a" until you get a sum "c" is a square? i.e. a + (1+3+5+7+9+11...) = c (where "c" is an integer square). Would this be quicker than the basic method? I have a worked example of this algorithm written in Rexx - where is a suitable place to post it? CG 80.229.220.254 (talk) 21:23, 28 May 2012 (UTC)[reply]

That would be a slower version of Fermat's factorization method, which is already too slow to be used in practice. CRGreathouse (t | c) 03:46, 29 May 2012 (UTC)[reply]

I do not see what the "Primes is in P" has to do with integer factorisation. Also, it seems illogical to have links to the Qsieve and MIRACL implementations without having direct links to state-of-the-art implementations such as MSIEVE (or YAFU), etc. — Preceding unsigned comment added by 86.30.148.199 (talk) 17:03, 26 December 2012 (UTC)[reply]

Why the technical flag, inserted May 25 2013? This article is about a mathematical concept and seems to define it well, with terms of less technicality, then proceed to describe various aspects of the concept and related concepts, some of which are quite technical. But why the technical flag when the concept itself is defined clearly in simpler terms so that someone familar with those simpler terms should have little difficulty understanding the subject of this article? There are many mathematical concepts of a level of technicality that will not be understood by someone unfamiliar with several prerequisites. Is this flag suggesting that we can and should write all articles in such a way that a two year old can understand them without any previous or additional research? — Anita5192 (talk) 04:44, 27 May 2013 (UTC)[reply]

I suggest adding a section containing a list of problems known to be equivalent to the problem of integer factorization. Such problems would include the breaking of the Rabin cryptosystem and of the Schmidt-Samoa cryptosystem. Knowledgeable people, please feel free to add. — Preceding unsigned comment added by 109.100.71.130 (talk) 16:47, 19 April 2014 (UTC)[reply]

Now, numbers less than how many bits can be factorized? ( 10 495 − 1 ) / 9 {\displaystyle (10^{495}-1)/9} has a 545-bit composite factor which doesn't have any known factors (See Factors of Repunit numbers), so the limit of bits must be less then 545 (That is, at most 544), but the limit of bits must be at least 200 (See Number factorizer), so I think the limit is 384 bits, but is it right? If not, what is the limit of bits? Is it 256? 320? or 512?

However, a Mersenne composite number 2 1061 − 1 {\displaystyle 2^{1061}-1} , which has 1061 bits(See Factorb) , has be factored, why can it be factored?

— Preceding unsigned comment added by 61.219.149.55 (talk) 06:30, 6 May 2014 (UTC)[reply]

There is no fixed limit and the used algorithms don't stop working at some size. They just require more computing power. The difficulty of factoring a number depends not only on the size of the number but also on the form of the number ( 2 n − 1 {\displaystyle 2^{n}-1} is easier than most others), and the size and sometimes other properties of its prime factors. And whether a number with a given difficulty is factored depends on how much computer time people are willing to spend on it, and sometimes on whether they get lucky. Integer factorization records#Numbers of a special form says one of the phases for 2 1061 − 1 {\displaystyle 2^{1061}-1} took about 300 CPU-years. RSA-768 on the same page says "They used the equivalent of almost 2000 years of computing on a single core 2.2 GHz AMD Opteron." Factoring is important in decryption so there is also the possibility that some organizations keep their capabilities secret. NSA#Computing has a lot of computing power and we don't know whether they have better algorithms than what is publicy known. PrimeHunter (talk) 23:57, 8 May 2014 (UTC)[reply]

But why the 545-bit number (884150927133......083700084281), which is a factor of 10^495-1, can't be factored? — Preceding unsigned comment added by 140.113.136.218 (talk) 04:33, 12 May 2014 (UTC)[reply]

As I said: "whether a number with a given difficulty is factored depends on how much computer time people are willing to spend on it". Apparently nobody has yet spend the time to factor this. It's non-trivial but certainly can be done. There are many people working on factoring bⁿ±1 for small b including 10, and they will surely get to this number at some time. If you are interested in factoring discussions then check out http://mersenneforum.org/. PrimeHunter (talk) 11:35, 12 May 2014 (UTC)[reply]

Also, even a tiny amount of research [1] would have shown that the number is mostly factored, with only a 164-digit cofactor. In any case take this discussion elsewhere, the purpose of the Talk pages is to build an encyclopedia not discuss ancillary topics. - CRGreathouse (t | c) 23:33, 14 May 2014 (UTC)[reply]

Complex Number Factoring is NPComplete

Subset Sum (given n integers, answer does any nonempty subset sum to 0) of n integers can be calculated as multiplying n complex numbers (each of magnitude 1) which are all scaled by the sum of all the integers so it can wrap around less than a half turn either direction in total.

The multiply of 2 complex numbers whose magnitude is 1 adds their angles around complex unit circle. Negative angle is the same as dividing by the positively angled complex number. Angle is normally ambiguous since it repeats on intervals of 2*pi, but since its scaled so it cant wrap around in total, each angle it can reach uniquely represents an integer.

Complex Number Factoring is NPComplete, based on that alone. Here's some more info...

If you multiply all the integers by 2, offset each of them by half their value, and move that value into the target sum of the subset to find, and do the same for the new target sum, then subset sum can be represented as a choice of negative or positive of the same value for each integer translated that way. On complex unit circle, it looks like rotating clockwise vs counterclockwise for each integer thats included or not. To solve Subset Sum you would factor 1.

Its not a root of unity. Its factors of unity limited to a set of possible factors.

It can also be represented as all being positive angled magnitude 1 complex numbers and looking for a Subset Multiply that equals that complex number.

Integer Factoring is to Multiply as Complex Number Factoring is to Plus. — Preceding unsigned comment added by 66.169.5.181 (talk) 19:53, 15 December 2014 (UTC)[reply]

a) This is wrong.

b) It is original research, and therefore not useful for WP.

--Macrakis (talk) 23:08, 15 December 2014 (UTC)[reply]

It's not even wrong. Absent any notion of unique factorization of complex numbers of norm 1 (i.e. on the unit circle) it's meaningless. The Gaussian integers do form a unique factorization domain but only four of them lie on the unit circle and all Gaussian primes lie strictly outside the unit circle. Vaughan Pratt (talk) 22:41, 19 March 2016 (UTC)[reply]

Are you quoting Pauli, Not even wrong? :-) Bubba73 ^{You talkin' to me?} 23:46, 19 March 2016 (UTC)[reply]

Yes, if stealing can be called quoting. ;) Vaughan Pratt (talk) 07:35, 2 May 2016 (UTC)[reply]

Does anyone else laugh when they get to that line? 68.2.235.85 (talk) —Preceding undated comment added 00:27, 6 June 2016 (UTC)[reply]

I would argue that factoring 15 did nothing to demonstrate their method. In binary 15 is 1111. The number 15 is 3×5, which in binary is computed 11×101, and is equivalent to writing 101+0101. In factoring 15, their was no untangling of the superposition of bits (or qbits) whatsoever!!!!! The bit pattern 101 just falls straight out of the pattern 1111. The claims made for Shor's algorithm are absurd at best. Runestone1 (talk) 01:09, 8 September 2016 (UTC)[reply]

Look at this presentation. Bosons1978 (talk) 15:32, 11 February 2021 (UTC)[reply]

This is a self published source, so it cannot be used in Wikipedia per policy WP:NOR. Moreover, I have had a quick look on the link, and it is almost immediately clear that the algorithm cannot be correct. Also, if it were correct and as fast as claimed, this would be cited in many articles, and even in news, which is not the case. D.Lazard (talk) 16:24, 11 February 2021 (UTC)[reply]

Unlike many other crank-magnet problems (e.g. P vs NP), there's a very very easy way to get taken seriously. Publish the factors of RSA-2048. If anyone does that, we can throw out WP:RS and WP:NOR out the window, per WP:SKYBLUE. I'm not holding my breath here, but has this author done so? Suffusion of Yellow (talk) 20:00, 11 February 2021 (UTC)[reply]

If its the same thing, then it is now now published as a paper in the International Association for Cryptologic Research journal by renown mathematician and cryptographer Claus P. Schnorr. HN discussion. Balupton (talk) 01:45, 3 March 2021 (UTC)[reply]

As it's now published in a journal. I've gone ahead and made an edit to the main page. Balupton (talk) 02:10, 3 March 2021 (UTC)[reply]

eprint.iacr.org is a preprint server, not a journal. As their homepage says, Papers have been placed here by the authors and did not undergo any refereeing process other than verifying that the work seems to be within the scope of cryptology. XOR'easter (talk) 02:18, 3 March 2021 (UTC)[reply]

Also, the text abstract and the one in the PDF itself don't match; in particular, the statement "This destroyes [sic] the RSA cryptosystem" was tacked on to the text version, which is iffy. A bit more eyebrow-raising is that the PDF is labeled work in progress 31.10.2019, while the author's website has what appears to be a more recent version, dated 04.03.2020. Something's off. XOR'easter (talk) 05:21, 3 March 2021 (UTC)[reply]

I agree. It is highly unlikely that the claim is correct, and it fails Wikipedia's verifiability standards. NealKoblitz (talk) 12:04, 5 March 2021 (UTC)[reply]

Just kidding, of course. But in the section "Prime decomposition" is the line b = a 2 − n = 4 = 2 b {\textstyle b={\sqrt {a^{2}-n}}={\sqrt {4}}=2b} , which is either (a) missing punctuation or more likely (b) has an extraneous 'b' at the end. Now I've done my share of factoring, but that was 50 yarn ago. Would someone more active kindly make the edit? Thanks, JohnH~enwiki (talk) 20:10, 19 July 2023 (UTC)[reply]

@JohnH~enwiki: I have removed the wrong b.[2] PrimeHunter (talk) 22:56, 19 July 2023 (UTC)[reply]