# US 2025/0094524 A1 · Electronic device and method for factorization of target number

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

- Number: US 2025/0094524 A1
- Document ID: US20250094524A1
- Status: Published application
- Kind: A1
- Application number: 18/495,169
- Filed: 2023-10-26
- Published: 2025-03-20
- Earliest claimed: 2023-09-18
- Assignees: Korea University Research and Business Foundation
- Applicants: Korea University Research and Business Foundation
- Inventors: Chulwoo KIM; Hyundo JUNG; Hyunjin KIM; Jinwoo JEON; Woojin LEE; Yohan CHOI
- Web page: https://patentgrep.com/patent/US20250094524A1

## CPC

- G06F 17/11: for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06F 5/01: for shifting, e.g. justifying, scaling, normalising {(digital stores in which the information is moved stepwise, e.g. shift-registers G11C19/00; digital stores in which the information circulates G11C21/00)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Provided is an electronic device for factorization of a target number. The electronic device includes an energy calculating circuit configured to generate input values for updating bits of a candidate number based on an energy function that has a minimum when the candidate number is a factor of the target number, and bit updating circuits corresponding to the bits of the candidate number, respectively.

## Claims

### Claim 1

An electronic device for factorization of a target number, the electronic device comprising:
an energy calculating circuit configured to generate input values for updating bits of a candidate number based on an energy function that has a minimum when the candidate number is a factor of the target number; and
bit updating circuits corresponding to the bits of the candidate number, respectively,
wherein the energy calculating circuit is further configured to receive bit values of the candidate number from the bit updating circuits and generate the input values based on the bit values of the candidate number, and
wherein a kth bit updating circuit of the bit updating circuits is configured to receive a kth input value for a kth bit of the candidate number from the energy calculating circuit, from among the input values, and update the kth bit of the candidate number based on the kth input value.

### Claim 2 (depends on 1)

The electronic device of claim 1, wherein the candidate number includes a first candidate number and a second candidate number, and
wherein the bit updating circuits are configured to:
update the first candidate number in a cycle for updating the first candidate number; and
update the second candidate number in a cycle for updating the second candidate number.

### Claim 3 (depends on 1)

The electronic device of claim 1, wherein the bit updating circuits further are configured to simultaneously update each bit of the candidate number.

### Claim 4 (depends on 1)

The electronic device of claim 1, further comprising a decision circuit configured to determine whether factorization of the target number is complete based on the candidate number.

### Claim 5 (depends on 4)

The electronic device of claim 4, wherein the decision circuit is further configured to determine whether factorization of the target number is complete by performing a modulo operation on the target number and the candidate number.

### Claim 6 (depends on 4)

The electronic device of claim 4, further comprising a sieving circuit configured to determine a final candidate number among the candidate number and odd numbers adjacent to the candidate number.

### Claim 7 (depends on 6)

The electronic device of claim 6, wherein the sieving circuit is further configured to determine, as the final candidate number, a number that is not a multiple of 3, a multiple of 5, and a multiple of 7 among the candidate number and the odd numbers adjacent to the candidate number.

### Claim 8 (depends on 6)

The electronic device of claim 6, wherein the decision circuit is further configured to determine whether factorization of the target number is complete by performing a modulo operation on the target number and the final candidate number.

### Claim 9 (depends on 1)

The electronic device of claim 1, wherein the energy calculating circuit includes an energy difference calculating circuit configured to calculate a difference between a value of the energy function when the kth bit of the candidate number is 0 and a value of the energy function when the kth bit of the candidate number is 1.

### Claim 10 (depends on 9)

The electronic device of claim 9, wherein the energy calculating circuit further includes an energy shifting circuit configured to generate the kth input value by performing a shift operation on output of the energy difference calculating circuit.

### Claim 11 (depends on 10)

The electronic device of claim 10, wherein the energy shifting circuit is further configured to perform the shift operation by cycling through predetermined shift values and using the shift values as a shift value.

### Claim 12 (depends on 10)

The electronic device of claim 10, wherein the energy shifting circuit is further configured to perform the shift operation by cycling through predetermined shift values in an order from a small value to a large value and using the shift values as a shift value.

### Claim 13 (depends on 1)

The electronic device of claim 1, wherein the kth bit updating circuit of the bit updating circuits is configured to update the kth bit of the candidate number to 0 or 1 based on a probability value corresponding to the kth input value.

### Claim 14 (depends on 1)

The electronic device of claim 1, wherein the candidate number includes a first candidate number and a second candidate number,
wherein, in a current cycle for updating the first candidate number and the second candidate number,
the energy calculating circuit is further configured to perform a first sub cycle of generating a first input value based on the first candidate number and the second candidate number,
the bit updating circuit is further configured to perform a second sub cycle of updating the first candidate number based on the first input value,
the energy calculating circuit is further configured to perform a third sub cycle of generating a second input value based on the first candidate number, which is updated in the second sub cycle, and the second candidate number, and
the bit updating circuit is further configured to perform a fourth sub cycle of updating the second candidate number based on the second input value.

### Claim 15 (depends on 14)

The electronic device of claim 14, further comprising a decision circuit configured to determine whether factorization of the target number is complete based on the first candidate number and the second candidate number,
wherein the decision circuit is further configured to:
determine whether factorization of the target number is complete based on the first candidate number, which is updated in a second sub cycle of the current cycle, between the second sub cycle of the current cycle and a second sub cycle of a next cycle; and
determine whether factorization of the target number is complete based on the second candidate number, which is updated in the fourth sub cycle of the current cycle, between the fourth sub cycle of the current cycle and a fourth sub cycle of the next cycle.

### Claim 16

A method for factorization of a target number, the method comprising a plurality of candidate update cycles for updating a first candidate number and a second candidate number,
wherein a current candidate update cycle of the plurality of candidate update cycles includes:
a first energy calculating cycle of generating first input values corresponding to bits of the first candidate number based on an energy function that has a minimum when the first candidate number and the second candidate number are factors of the target number;
a first bit updating cycle of updating a bit of the first candidate number based on a corresponding first input value, for each of the bits of the first candidate number;
a second energy calculating cycle of generating second input values corresponding to bits of the second candidate number based on the energy function; and
a second bit updating cycle of updating a bit of the second candidate number based on a corresponding second input value, for each of the bits of the second candidate number.

### Claim 17 (depends on 16)

The method of claim 16, wherein the first energy calculating cycle includes:
calculating a difference between a value of the energy function when a kth bit of the first candidate number is 0 and a value of the energy function when the kth bit of the first candidate number is 1; and
generating a kth first input value corresponding to the kth bit of the first candidate number by performing a shift operation on the calculated difference for the first candidate number.

### Claim 18 (depends on 17)

The method of claim 17, wherein the second energy calculating cycle includes:
calculating a difference between a value of the energy function when a kth bit of the second candidate number is 0 and a value of the energy function when the kth bit of the second candidate number is 1; and
generating a kth second input value corresponding to the kth bit of the second candidate number by performing a shift operation on the calculated difference for the second candidate number.

### Claim 19 (depends on 18)

The method of claim 18, wherein the generating of the kth first input value includes performing the shift operation by alternately cycling through predetermined shift values and using the shift values every candidate update cycle among the plurality of candidate update cycles, and
wherein the generating of the kth second input value includes performing the shift operation using the shift values that are equal to a value in the generating of the kth first input value.

### Claim 20 (depends on 16)

The method of claim 16, wherein the first bit updating cycle includes updating the bit of the first candidate number to 0 or 1 based on a probability value corresponding to the corresponding first input value for each of the bits of the first candidate number.

### Claim 21 (depends on 16)

The method of claim 16, wherein the second bit updating cycle includes updating the bit of the second candidate number to 0 or 1 based on a probability value corresponding to the corresponding second input value for each of the bits of the second candidate number.

### Claim 22 (depends on 16)

The method of claim 16, wherein the current candidate update cycle includes:
a first sieving cycle of determining a first final candidate number among the first candidate number updated in the first bit updating cycle and odd numbers adjacent to the updated first candidate number, the first sieving cycle being between the first bit updating cycle and the second energy calculating cycle; and
a second sieving cycle of determining a second final candidate number among the second candidate number updated in the second bit updating cycle and odd numbers adjacent to the updated second candidate number, the second sieving cycle being after the second bit updating cycle.

### Claim 23 (depends on 22)

The method of claim 22, further comprising:
a first decision cycle of determining whether factorization of the target number is complete based on the first final candidate number, the first decision cycle being between the first sieving cycle of the current candidate update cycle and a first sieving cycle of a next candidate update cycle; and
a second decision cycle of determining whether factorization of the target number is complete based on the second final candidate number, the second decision cycle being between the second sieving cycle of the current candidate update cycle and a second sieving cycle of the next candidate update cycle.

### Claim 24 (depends on 16)

A computer-readable recording medium having recorded thereon a program for executing the method of claim 16.
