# Does the security of RSA come from just the carries in multiplication?

Although it's hard for me to find a reference, it's my understanding that if you calculate $$N = pq$$ using $$GF(2)$$ polynomial multiplication rather than ordinary multiplication, it is easy to factor $$N$$ under this type of multiplication.

I might have the terminology wrong when I say "$$GF(2)$$ polynomial multiplication". I mean carryless or "XOR" multiplication done in base 2.

Is this true, and if so, does it mean that the security of RSA comes entirely from the addition carries that happen during ordinary multiplication?

• The wording is strange. Indeed, factoring without carries (over GF(2)) is easy. Adding carries makes it hard. But it is the whole thing that is hard, not the carries themselves. May 7 at 20:19

might have the terminology wrong when I say "GF(2) polynomial multiplication"

You are thinking of multiplication in the ring of binary polynomials, that is polynomials with coefficients in the Galois Field with 2 elements. That set is noted $$GF(2)[x]$$. It's addition reduces to XOR of the coefficients of equal weight. It's multiplication is called "carryless multiplication" in computing. It supports an analog to Euclidean division, and modular arithmetic.

It's my understanding that if you calculate $$N=pq$$ using (this) multiplication rather than ordinary multiplication, it is easy to factor $$N$$.

Yes. There are efficient algorithms for factoring binary polynomials into irreducible polynomials (which are analogs to primes in the ring of binary polynomials).

Does it mean that the security of RSA comes entirely from the addition carries that happen during ordinary multiplication?

True, RSA is not secure if we remove the carries (in the additions within it's multiplication by the schoolbook algorithm). I can't agree with "security .. comes entirely". Analogy: a chain is insecure if one removes it's last link, yet it's security does not come entirely from that link.

• Computing seems to give it at least three different names: "carryless multiplication" (x86), "polynomial multiplication" (ARM), "XOR multiplication" (SPARC). I'm a programmer by trade, so those were the names most natural to me, not the correct term. Sorry for the weird wording! May 7 at 20:26
• @Myria: yes, I have often met "(binary) polynomial multiplication". If did now knew "XOR multiplication", but then I'm utterly unfamiliar with SPARC, and it's perfectly logical: binary polynomial multiplication can be obtained by changing binary addition to XOR in the usual binary multiplication algorithm.
– fgrieu
May 7 at 20:31
• Algebrae over GF(2) and over natural integers are two completely different topics!
– iBug
May 8 at 4:05
• I'd say the absence of carries makes quite some differences. For example, if we list a set of formulae for addition of two numbers, we'll see that the highest bit of the sum can depend on every input bit in $\mathbb Z$, while in GF(2)[x] it depends only on the same bits of input (reduction in complexity). Also, any element in GF(2)[x] is its own additive inverse, and the invalidation of Peano arithmetic, which gives multiplication a completely different nature since it's no longer "repetition of addition".
– iBug
May 8 at 6:27
• I'm not to argue that your answer is wrong, but that the question is intrinsically flawed. Granted, arithmetic over $GF(2^n)$ is useful in other contexts, but when it comes to RSA, it's just like comparing apples to oranges.
– iBug
May 8 at 6:32