# US 2026/0312807 A1 · Generation of prime numbers subject to an auxiliary condition in cryptographic applications

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2026/0312807 A1
- Document ID: US20260312807A1
- Status: Published application
- Kind: A1
- Application number: 19/635,143
- Filed: 2026-03-31
- Published: 2026-10-08
- Earliest claimed: 2025-04-03
- Assignees: Cryptography Research, Inc.
- Applicants: Cryptography Research, Inc.
- Inventors: Qinglai Xiao; Michael Alexander Hamburg
- Web page: https://patentgrep.com/patent/US20260312807A1

## CPC

- H04L 9/3033: {details relating to pseudo-prime or prime number generation, e.g. primality test}
- G06F 7/722: {Modular multiplication (G06F7/724, G06F7/727, G06F7/728 take precedence)}
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Aspects of the present disclosure involve a method, a system and a computer readable memory to generate and use prime numbers in cryptographic applications using operations that include selecting a subset of prime numbers and identifying polynomial function(s) that (i) have no roots modulo each of the subset of prime numbers and (ii) generate outputs that are congruent to a predetermined value modulo a reference value. The operations further include selecting one or more input values, applying the one or more polynomial function(s) to the one or more input values to generate a candidate number, determining that the candidate number is a prime number, and computing using the determined prime number, an output of a cryptographic operation.

## Claims

### Claim 1

A method to perform a cryptographic operation, the method comprising:
selecting a subset of prime numbers;
identifying, by a processing device, one or more polynomial functions that (i) have no roots modulo each prime number of the selected subset of prime numbers and (ii) generate outputs that are congruent to a predetermined value modulo a reference value;
selecting, by the processing device, one or more input values;
applying, by the processing device, the one or more polynomial functions to the one or more input values to generate a candidate number;
determining, by the processing device, that the candidate number is a prime number; and
computing, by the processing device and using the determined prime number, an output of a cryptographic operation.

### Claim 2 (depends on 1)

The method of claim 1, wherein the one or more polynomial functions comprise a quadratic function associated with:
a first coefficient determined using (i) a quadratic nonresidue modulo each of the selected subset of prime numbers, and (ii) the reference value, and
a second coefficient determined using the predetermined value.

### Claim 3 (depends on 1)

The method of claim 1, wherein a number of the one or more input values is at least four.

### Claim 4 (depends on 1)

The method of claim 1, wherein applying the one or more polynomial functions to the one or more input values to generate the candidate number comprises:
computing a product of a plurality of intermediate values, each intermediate value of the plurality of intermediated values computed by applying a polynomial function of the one or more polynomial functions to an input value of the one or more input values.

### Claim 5 (depends on 4)

The method of claim 4, wherein the product of the plurality of intermediate values is computed modulo a modulus number divisible by each of the subset of prime numbers.

### Claim 6 (depends on 5)

The method of claim 5, wherein the product of the plurality of intermediate values is computed using Montgomery multiplication.

### Claim 7 (depends on 1)

The method of claim 1, wherein the one or more input values are selected within a predetermined interval using a pseudorandom function in view of one or more stored values.

### Claim 8 (depends on 1)

The method of claim 1, wherein the predetermined value is a unit value.

### Claim 9 (depends on 1)

The method of claim 1, wherein the reference value comprises a prime number different from each prime number of the subset of prime numbers.

### Claim 10 (depends on 1)

The method of claim 1, wherein each of the one or more polynomial functions generate outputs that are congruent to the predetermined value modulo the reference value for all inputs into a respective polynomial function of the one or more polynomial functions.

### Claim 11 (depends on 1)

The method of claim 1, wherein the output of the cryptographic operation comprises at least one of:
a digital signature for an input into the cryptographic operation,
an encryption of the input into the cryptographic operation, or
a decryption of the input into the cryptographic operation.

### Claim 12

A system comprising:
a memory device; and
a processing device communicatively coupled to the memory device, the processing device to:
select a subset of prime numbers;
identify one or more polynomial functions that (i) have no roots modulo each prime number of the selected subset of prime numbers and (ii) generate outputs that are congruent to a predetermined value modulo a reference value;
select one or more input values;
apply the one or more polynomial functions to the one or more input values to generate a candidate number;
determine that the candidate number is a prime number; and
compute, using the determined prime number, an output of a cryptographic operation.

### Claim 13 (depends on 12)

The system of claim 12, wherein the one or more polynomial functions comprise a quadratic function associated with:
a first coefficient determined using (i) a quadratic nonresidue modulo each of the selected subset of prime numbers, and (ii) the reference value, and
a second coefficient determined using the predetermined value.

### Claim 14 (depends on 12)

The system of claim 12, wherein to apply the one or more polynomial functions to the one or more input values to generate the candidate number, the processing device is to:
compute a product of a plurality of intermediate values, each intermediate value of the plurality of intermediated values computed by applying a polynomial function of the one or more polynomial functions to an input value of the one or more input values.

### Claim 15 (depends on 14)

The system of claim 14, wherein the product of the plurality of intermediate values is computed modulo a modulus number divisible by each of the subset of prime numbers.

### Claim 16 (depends on 15)

The system of claim 15, wherein the product of the plurality of intermediate values is computed using Montgomery multiplication.

### Claim 17 (depends on 12)

The system of claim 12, wherein the one or more input values are selected within a predetermined interval using a pseudorandom function in view of one or more stored values.

### Claim 18 (depends on 12)

The system of claim 12, wherein the reference value comprises a prime number different from each prime number of the subset of prime numbers.

### Claim 19 (depends on 12)

The system of claim 12, wherein the output of the cryptographic operation comprises at least one of:
a digital signature for an input into the cryptographic operation,
an encryption of the input into the cryptographic operation, or
a decryption of the input into the cryptographic operation.

### Claim 20

A non-transitory computer-readable medium storing instructions thereon, wherein the instructions, when executed by a processing device performing a cryptographic operation, cause the processing device to:
select a subset of prime numbers;
identify one or more polynomial functions that (i) have no roots modulo each prime number of the selected subset of prime numbers and (ii) generate outputs that are congruent to a predetermined value modulo a reference value;
select one or more input values;
apply the one or more polynomial functions to the one or more input values to generate a candidate number;
determine that the candidate number is a prime number; and
compute, using the determined prime number, an output of a cryptographic operation.
