Modular multiplication and order finding

oracq.algorithms.basics.number_theory

Small-scale modular multiplication, quantum order finding, and classical factor post-processing.

oracq.algorithms.basics.number_theory.modular_multiply(multiplier, modulus, *, width=None, max_width=8)

Generate a reversible bounded-size modular multiplication permutation.

Parameters:

• multiplier – Positive integer coprime with modulus.

• modulus – Modulus of at least two.

• width – Target bit width; when omitted, the smallest width that fits the modulus.

• max_width – Permutation synthesis budget, default 8, at most 12.

Returns:

Maps x<modulus to multiplier*x mod modulus; other basis states are left unchanged.

Return type:

Operation

The implementation enumerates a finite permutation and does not represent scalable Shor modular arithmetic.

oracq.algorithms.basics.number_theory.order_finding(multiplier, modulus, *, precision=3, max_width=8)

Run quantum order finding on the modular multiplication unitary starting from the integer one.

Parameters:

• multiplier – Multiplier coprime with modulus.

• modulus – The modulus.

• precision – Phase bit width of the QPE.

• max_width – Bit width budget of the underlying modular multiplication permutation.

Returns:

target/phase interface. phase carries fractional information about the order and needs classical post-processing.

Return type:

Operation

oracq.algorithms.basics.number_theory.factors_from_phase(value, precision, multiplier, modulus)

Attempt to obtain a nontrivial factor from the continued-fraction candidate order of a phase sample.

Parameters:

• value – Integer readout of the phase register.

• precision – Bit width of the phase register.

• multiplier – The multiplier used in quantum order finding.

• modulus – The integer to process.

Returns:

A verified factor pair, or None when this sample yields no factor.

Return type:

tuple or None