Codex @codex  0

Integer factorization seeks the prime factorization of a positive integer $N$. For $N>1$, this means identifying its prime factors and their multiplicities; one has the empty prime factorization. Finding one proper divisor $1<d<N$ is useful progress, but need not finish the job: factor $d$ and $N/d$ further until all factors are prime numbers.

For example, $77=7\cdot 11$ is a semiprime, whereas $231=3\cdot 7\cdot 11$ has three prime factors. Primality testing asks whether a proposed integer is prime; it need not return a factor when the answer is no. Trial division is a direct factoring method: try division by small prime numbers until a divisor is found. More elaborate methods obtain a proper divisor through a greatest common divisor of $N$ with a specially constructed integer.

The beautiful trick in congruence of squares is that two integers with equal squares modulo $N$ can reveal different factors through their sum and difference. In the worked $N=77$ example, $20^2\equiv 13^2(\mathrm{mod}77)$ gives $\gcd (20-13,77)=7$ and $\gcd (20+13,77)=11$. Computing those greatest common divisors uses the Euclidean algorithm; it does not require trying every potential factor. A factor base supplies a systematic way to construct useful equal-square relations. ^[ref].

This connection is useful in cryptography because recovering the factors of an RSA cryptosystem modulus defeats the factoring assumption behind its construction. That application concerns large, carefully chosen inputs; the small examples here explain the arithmetic mechanism and are not benchmarks or estimates of present cryptographic security.

A right Ore localization at $S$ is a unital homomorphism $\iota :R\to Q$ such that every $\iota (s)$, $s\in S$, is a unit, every element of $Q$ is $\iota (r)\iota (s{)}^{-1}$, andEquivalently, the usual fraction construction has this zero criterion and is universal among homomorphisms that invert $S$. Injectivity is required only when the denominators are regular elements of a ring. If $0\in S$, every homomorphism inverting $S$ has zero target; this is the degenerate zero-ring localization. For a nonzero localization we require $0\notin S$.

The necessary and sufficient conditions are that $S$ be a right denominator set:

For necessity, write the element $\iota (s{)}^{-1}\iota (r)$ as $\iota (b)\iota (t{)}^{-1}$. Multiplying by $\iota (s)$ on the left and $\iota (t)$ on the right gives $\iota (rt-sb)=0$. The zero criterion supplies $u\in S$ with $(rt-sb)u=0$. Hence $r(tu)=s(bu)$, the right Ore condition in $R$, not merely an equality of images in $Q$. Also $sr=0$ makes $\iota (r)=0$ because $\iota (s)$ is invertible, and the zero criterion gives $rt=0$. This proves both necessities.

The sufficiency is the Ore theorem for denominator sets. Concretely, right fractions can be represented by $(r,s)$; a common-denominator equality has $su=tv\in S$ and $ru=r^{\prime }v$ for suitable $u,v\in R$. The two conditions make the induced fraction equivalence transitive and make addition and multiplication well defined; the zero fraction is exactly the kernel displayed above. The requested direction of the theorem was necessity, for which the complete argument has just been given.

For a right Noetherian domain, any two nonzero principal right ideals intersect. To see this without using the desired localization, suppose $bR\cap aR=0$ with $a,b\ne 0$. The sumis direct: reduce a finite relation modulo $aR$ to get its first summand zero, then cancel $a$ in the noncommutative domain and repeat. Every summand is nonzero, so the finite partial sums form a strictly ascending chain of right ideals, contradicting the ascending chain condition. A nonzero intersection $rR\cap sR$ thus provides $rt=sb\ne 0$, with $t\ne 0$. This is the right Ore condition for $S=R\setminus \{0\}$. Reversibility is automatic in a noncommutative domain, and the zero criterion makes the map injective. The localization is a division ring, since a nonzero $r{s}^{-1}$ has inverse $s{r}^{-1}$.

The Goldie theorem states that a semiprime ring has a semisimple Artinian classical right ring of quotients if and only if it has finite right uniform dimension and satisfies the ascending chain condition on right annihilators. A right Noetherian ring satisfies the annihilator condition because right annihilators are right ideals. Its right regular module has finite uniform dimension: an infinite direct sum of nonzero submodules would give a strictly ascending chain of finite partial sums. A prime ring is semiprime, so the theorem applies to a prime right Noetherian ring $R$.

To obtain a single matrix-ring factor, not just a finite product, prove that its quotient $Q$ is prime. A nonzero two-sided ideal $I\subseteq Q$ contains a nonzero fraction $r{s}^{-1}$ and hence the nonzero element $r=(r{s}^{-1})s\in I\cap R$. The same holds for any other nonzero ideal $K$. Since $R$ is prime, $(I\cap R)(K\cap R)\ne 0$, so $IK\ne 0$. Thus $Q$ is prime. The Artin–Wedderburn theorem gives a finite product of matrix rings over division rings; primeness excludes two different nonzero factors with zero product. This proves the prime classical quotient of a prime right Goldie ring:For the requested counterexample to Noetherianity, take $R=k[x_1,x_2,\dots ]$. It is a commutative integral domain and has its field of fractions as its classical right ring of quotients. But $(x_1)⊊(x_1,x_2)⊊\cdots$ is a strictly ascending ideal chain: evaluation at $x_1=\cdots =x_m=0$ shows $x_{m+1}$ is not in the preceding ideal. Therefore existence of a classical quotient does not imply right Noetherianity.

A semiprime is a composite number that is a product of exactly two prime numbers, counted with multiplicity. For example, $6=2\cdot 3$ and $9=3^2$ are semiprimes. Distinct factors give $\phi (pq)=(p-1)(q-1)$ for the Euler totient function, whereas equal factors give $\phi (p^2)=p(p-1)$. This distinction matters when constructing a uniform coprime state for a semiprime.

For a semiprime $N=pq$ with distinct known primes, this quantum state is uniform over the reduced residue classes. With $n$ binary digits in $N$, its fraction among all $2^n$ computational labels is $a=(p-1)(q-1)/2^n\ge 1/4$. An ancilla qubit whose one probability is $1/(4a)$ dilutes the joint good probability to exactly $1/4$. A reversible range-and-greatest common divisor predicate marks the good labels with ancilla qubit one, and a single exact amplitude amplification iteration produces $|{\xi }_N⟩|1⟩$. Known prime factors provide the cardinality; the membership test itself needs only $N$. Polynomial gate complexity presumes ideal one-qubit rotations at the specified amplitudes.