Modular Multiplication

from qualtran import Bloq, CompositeBloq, BloqBuilder, Signature, Register
from qualtran import QBit, QInt, QUInt, QAny
from qualtran.drawing import show_bloq, show_call_graph, show_counts_sigma
from typing import *
import numpy as np
import sympy
import cirq

ModDbl

An n-bit modular doubling gate.

Implements \(\ket{x} \rightarrow \ket{2x \mod p}\) using \(2n\) Toffoli gates.

Parameters

• dtype: Dtype of the number to double.

• p: The modulus for the doubling.

Registers

• x: The register containing the number to double.

References

• How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates. Fig 6d and 8

from qualtran.bloqs.mod_arithmetic import ModDbl

Example Instances

moddbl_small = ModDbl(QUInt(4), 13)

prime = 10**9 + 7
moddbl_large = ModDbl(QUInt(32), prime)

Graphical Signature

from qualtran.drawing import show_bloqs
show_bloqs([moddbl_small, moddbl_large],
           ['`moddbl_small`', '`moddbl_large`'])

Call Graph

from qualtran.resource_counting.generalizers import ignore_split_join
moddbl_small_g, moddbl_small_sigma = moddbl_small.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(moddbl_small_g)
show_counts_sigma(moddbl_small_sigma)

Counts totals:

• AddK: 1

• CNOT: 1

• C[AddK]: 1

• X: 2

CModMulK

Perform controlled modular multiplication by a constant.

Applies \(\ket{c}\ket{x} \rightarrow \ket{c} \ket{x*k^c \mod p}\).

Parameters

• dtype: Dtype of the register.

• k: The integer multiplicative constant.

• mod: The integer modulus.

Registers

• ctrl: The control bit

• x: The integer being multiplied

from qualtran.bloqs.mod_arithmetic import CModMulK

Example Instances

import sympy

k, N, n_x = sympy.symbols('k N n_x')
modmul_symb = CModMulK(QUInt(n_x), k=k, mod=N)

modmul = CModMulK(QUInt(8), k=123, mod=13 * 17)

Graphical Signature

from qualtran.drawing import show_bloqs
show_bloqs([modmul_symb, modmul],
           ['`modmul_symb`', '`modmul`'])

Call Graph

from qualtran.resource_counting.generalizers import ignore_split_join
modmul_symb_g, modmul_symb_sigma = modmul_symb.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(modmul_symb_g)
show_counts_sigma(modmul_symb_sigma)

Counts totals:

• CSwap: 1

• CtrlScaleModAdd: 2

DirtyOutOfPlaceMontgomeryModMul

Perform windowed montgomery modular multiplication.

Applies the trasformation

\[ \ket{x}\ket{y}\ket{0}\ket{0}\ket{0} \rightarrow \ket{x}\ket{y}\ket{xy2^{-n}}\ket{h}\ket{c} \]

Where:

• \(n\) is the bitsize.

• \(x, y\) are in montgomery form

• \(h\) is an ancilla register that represents intermidate values.

• \(c\) is whether a final modular reduction was applied or not.

Parameters

• bitsize: size of the numbers.

• window_size: size of the window.

• mod: The integer modulus.

• uncompute: whether to compute or uncompute.

Registers

• x: The first integer

• y: The second integer

• target: product in montgomery form \(xy 2^{-n}\)

• qrom_indices: concatination of the indicies used to query QROM.

• reduced: whether a final modular reduction was applied.

References

• Performance Analysis of a Repetition Cat Code Architecture: Computing 256-bit Elliptic Curve Logarithm in 9 Hours with 126 133 Cat Qubits. Appendix C4.

• How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates. page 8.

from qualtran.bloqs.mod_arithmetic import DirtyOutOfPlaceMontgomeryModMul

Example Instances

dirtyoutofplacemontgomerymodmul_small = DirtyOutOfPlaceMontgomeryModMul(6, 2, 7)

dirtyoutofplacemontgomerymodmul_medium = DirtyOutOfPlaceMontgomeryModMul(
    bitsize=16, window_size=4, mod=2**15 - 1
)

Graphical Signature

from qualtran.drawing import show_bloqs
show_bloqs([dirtyoutofplacemontgomerymodmul_small, dirtyoutofplacemontgomerymodmul_medium],
           ['`dirtyoutofplacemontgomerymodmul_small`', '`dirtyoutofplacemontgomerymodmul_medium`'])

Call Graph

from qualtran.resource_counting.generalizers import ignore_split_join
dirtyoutofplacemontgomerymodmul_small_g, dirtyoutofplacemontgomerymodmul_small_sigma = dirtyoutofplacemontgomerymodmul_small.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(dirtyoutofplacemontgomerymodmul_small_g)
show_counts_sigma(dirtyoutofplacemontgomerymodmul_small_sigma)

Counts totals:

• C[AddK]: 1

• LessThanConstant: 1

• SingleWindowModMul: 3

• X: 1