Electronic device and method for factorization of target number

Patent metadata

Field	Value
Publication number	US-2025094524-A1
Application number	US-202318495169-A
Country	US
Kind code	A1
Filing date	Oct 26, 2023
Priority date	Sep 18, 2023
Publication date	Mar 20, 2025
Grant date	—

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.

First claim

What is claimed is:

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 k th bit updating circuit of the bit updating circuits is configured to receive a k th input value for a k th bit of the candidate number from the energy calculating circuit, from among the input values, and update the k th bit of the candidate number based on the k th input value.

2 . 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.

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

4 . 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.

5 . 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.

6 . 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.

7 . 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.

8 . 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.

9 . 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 k th bit of the candidate number is 0 and a value of the energy function when the k th bit of the candidate number is 1.

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

11 . 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.

12 . 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.

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

14 . 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.

15 . 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.

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.

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

18 . The method of claim 17 , wherein the second energy calculating cycle includes:
calculating a difference between a value of the energy function when a k th bit of the second candidate number is 0 and a value of the energy function when the k th bit of the second candidate number is 1; and generating a k th

Assignees

• Univ Korea Res & Bus Found

Inventors

• Kim Chulwoo
• Jung Hyundo
• Kim Hyunjin
• Jeon Jinwoo
• Lee Woojin
• Choi Yohan

Classifications

• G06F7/74

  Selecting or encoding within a word the position of one or more bits having a specified value, e.g. most or least significant one or zero detection, priority encoders {(with shifting G06F5/01)} · CPC title

• G06F5/01 Primary

  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)} · CPC title

• G06F17/16 Primary

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• G06F17/11 Primary

  for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title