Skip to content

Latest commit

 

History

History
202 lines (161 loc) · 15.8 KB

factoring.md

File metadata and controls

202 lines (161 loc) · 15.8 KB

Examples: Factoring integers

Prerequisites

Launch Sage and load the factoring.sage script by executing:

$ sage
(..)
sage: load("factoring.sage")

Simulating the quantum algorithm

To simulate factoring an integer $N$ of length $n$ bits with $t$ distinct prime factors, each of length $l$ bits, first setup such an integer on special form by executing:

sage: [N, factors] = sample_integer(t = 2, l = 1024, verbose = True)
Sampling N on special form to enable efficient simulation...
 Sampled factor: 91594495837132130502479897400388304634693378530549458696319460444396358275315967809701370732397682460986376374359082244551494222333169133490760259641273466780051477229600820460450746811728768148207749193286310793431171871537115927006068876327350290260773844078660243151253787463756407455838446265225918046583
 Sampled factor: 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947

 Sampled N = 10973832863201673753319620514211024850976747028877316641007348621885069761326964846903319534510204377723795042572907874450063354411384196564115340622443166583065103541222563874815142098657655166050108598305054310470303212014268786830970462132785070371598885421626356117473557448926507224965198275919202894828964925715894545729780135359329322925505502812930724077166991080955916772302205391974242990997373159923870406984876301328370758011305027899671421668861677490250772532546342549902812310763878482303815217849847491014791537509903158316008667203979777196241566771198921018713208866502285052348318258910115106723101

 Time required to sample: 120 ms 584 µs
sage: n = N.nbits()

This yields $N$ and the prime factors of $N$.

Next, generate a basis for the $d$-dimensional lattice for this problem instance, where $d = \lceil \sqrt{n} \rceil$, by executing:

sage: d = ceil(sqrt(n))
sage: B = generate_basis_for_factoring(N, factors, d = d, verbose = True)
Generating a basis for the lattice L...
 Sampling vectors from L...
  Sampling vectors 1 to 8 of 54 using 8 threads...
  Sampling vectors 9 to 16 of 54 using 8 threads...
  Sampling vectors 17 to 24 of 54 using 8 threads...
  Sampling vectors 25 to 32 of 54 using 8 threads...
  Sampling vectors 33 to 40 of 54 using 8 threads...
  Sampling vectors 41 to 48 of 54 using 8 threads...
  Sampling vectors 49 to 54 of 54 using 8 threads...

 Reducing the basis for L, this may take a moment...

 Time required to generate a basis for L: 1 min 39 sec 512 ms 332 µs

This basis can then be used to setup the simulator by executing:

sage: simulator = Simulator(B, verbose = True)
Setting up the simulator...
 Computing the basis for the dual L^* of L...
 Computing the Gram–Schmidt orthogonalization of the basis...

 Time required to setup the simulator: 7 sec 926 ms 247 µs

Finally, simulate running the quantum algorithm $d + 4$ times with $C = 2$ by executing:

sage: R = get_regev_R(C = 2, n = N.nbits())
sage: samples = simulator.sample_vectors(R = R, verbose = True)
Sampling 50 good vectors and 0 bad vectors...
 Sampling vectors 1 to 8 of 50 using 8 threads...
 Sampling vectors 9 to 16 of 50 using 8 threads...
 Sampling vectors 17 to 24 of 50 using 8 threads...
 Sampling vectors 25 to 32 of 50 using 8 threads...
 Sampling vectors 33 to 40 of 50 using 8 threads...
 Sampling vectors 41 to 48 of 50 using 8 threads...
 Sampling vectors 49 to 50 of 50 using 2 threads...

 Time required to sample: 4 sec 564 ms 136 µs

Executing the classical post-processing

To solve the samples for the factors of $N$, execute:

sage: factors = solve_samples_for_factors(samples, N, R, verbose = True)
Post-processing the sampled vectors to find factors...
 Building the post-processing matrix...
 Running LLL on the post-processing matrix...

 Processing the factoring relations found...
  Found factor: 91594495837132130502479897400388304634693378530549458696319460444396358275315967809701370732397682460986376374359082244551494222333169133490760259641273466780051477229600820460450746811728768148207749193286310793431171871537115927006068876327350290260773844078660243151253787463756407455838446265225918046583
  Found factor: 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947
  Found factor: 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947
  Found factor: 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947
  Found factor: 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947
  Found factor: 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947
  Found factor: 91594495837132130502479897400388304634693378530549458696319460444396358275315967809701370732397682460986376374359082244551494222333169133490760259641273466780051477229600820460450746811728768148207749193286310793431171871537115927006068876327350290260773844078660243151253787463756407455838446265225918046583
  Found factor: 91594495837132130502479897400388304634693378530549458696319460444396358275315967809701370732397682460986376374359082244551494222333169133490760259641273466780051477229600820460450746811728768148207749193286310793431171871537115927006068876327350290260773844078660243151253787463756407455838446265225918046583
  Found factor: 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947
  Found factor: 91594495837132130502479897400388304634693378530549458696319460444396358275315967809701370732397682460986376374359082244551494222333169133490760259641273466780051477229600820460450746811728768148207749193286310793431171871537115927006068876327350290260773844078660243151253787463756407455838446265225918046583
  Found factor: 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947
  Found factor: 91594495837132130502479897400388304634693378530549458696319460444396358275315967809701370732397682460986376374359082244551494222333169133490760259641273466780051477229600820460450746811728768148207749193286310793431171871537115927006068876327350290260773844078660243151253787463756407455838446265225918046583
  Found factor: 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947
  Found factor: 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947
  Found factor: 91594495837132130502479897400388304634693378530549458696319460444396358275315967809701370732397682460986376374359082244551494222333169133490760259641273466780051477229600820460450746811728768148207749193286310793431171871537115927006068876327350290260773844078660243151253787463756407455838446265225918046583
  Found factor: 91594495837132130502479897400388304634693378530549458696319460444396358275315967809701370732397682460986376374359082244551494222333169133490760259641273466780051477229600820460450746811728768148207749193286310793431171871537115927006068876327350290260773844078660243151253787463756407455838446265225918046583
  Found factor: 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947
  Found factor: 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947
  Found factor: 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947
  Found factor: 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947
  Found factor: 91594495837132130502479897400388304634693378530549458696319460444396358275315967809701370732397682460986376374359082244551494222333169133490760259641273466780051477229600820460450746811728768148207749193286310793431171871537115927006068876327350290260773844078660243151253787463756407455838446265225918046583
  Found factor: 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947
  Found factor: 91594495837132130502479897400388304634693378530549458696319460444396358275315967809701370732397682460986376374359082244551494222333169133490760259641273466780051477229600820460450746811728768148207749193286310793431171871537115927006068876327350290260773844078660243151253787463756407455838446265225918046583
  Found factor: 91594495837132130502479897400388304634693378530549458696319460444396358275315967809701370732397682460986376374359082244551494222333169133490760259641273466780051477229600820460450746811728768148207749193286310793431171871537115927006068876327350290260773844078660243151253787463756407455838446265225918046583

 Time required to post-process: 12 sec 610 ms 257 µs
sage: print(f"Found the following collection of factors:\n{factors}")
Found the following collection of factors:
{91594495837132130502479897400388304634693378530549458696319460444396358275315967809701370732397682460986376374359082244551494222333169133490760259641273466780051477229600820460450746811728768148207749193286310793431171871537115927006068876327350290260773844078660243151253787463756407455838446265225918046583, 119808868021007384928573228253206333635140879247951559997473560043741354712633463551955802705029051057190475499478912524974615985445775089407415527776908008771213178934959980796156462827943569216974884348803945894213691806127539272290979018784826433283592101497502259083087247481938351590931419447957964423947}
sage: print(f"Found the complete factorization: {factors.is_complete()}")
Found the complete factorization: True

Convenience test function

There is also a convenience test function that performs the above procedure given $t$ and $l$.

To try it out, execute:

sage: factors = test_factoring(t = 8, l = 32, verbose = True)
** Setting up the problem instance...

Sampling N on special form to enable efficient simulation...
 Sampled factor: 3122409359
 Sampled factor: 3095419463
 Sampled factor: 2274966587
 Sampled factor: 4248511859
 Sampled factor: 2721757583
 Sampled factor: 3322961963
 Sampled factor: 3293073263
 Sampled factor: 2572131767

 Sampled N = 7156334365464253025080708612081116077834975417905653732721337043535190145349

 Time required to sample: 56 ms 696 µs

** Setting up the simulator...

Generating a basis for the lattice L...
 Sampling vectors from L...
  Sampling vectors 1 to 8 of 24 using 8 threads...
  Sampling vectors 9 to 16 of 24 using 8 threads...
  Sampling vectors 17 to 24 of 24 using 8 threads...

 Reducing the basis for L, this may take a moment...

 Time required to generate a basis for L: 181 ms 895 µs

Setting up the simulator...
 Computing the basis for the dual L^* of L...
 Computing the Gram–Schmidt orthogonalization of the basis...

 Time required to setup the simulator: 36 ms 246 µs

** Using the simulator to sample vectors...

Sampling 20 good vectors and 0 bad vectors...
 Sampling vectors 1 to 8 of 20 using 8 threads...
 Sampling vectors 9 to 16 of 20 using 8 threads...
 Sampling vectors 17 to 20 of 20 using 4 threads...

 Time required to sample: 114 ms 657 µs

** Post-processing the sampled vectors to find factors...

Post-processing the sampled vectors to find factors...
 Building the post-processing matrix...
 Running LLL on the post-processing matrix...

 Processing the factoring relations found...
  Found factor: 100282942232670733753564463342679165061
  Found factor: 224841965849297529750007832925644712442766392331
  Found factor: 23189742393865049067664984403
  Found factor: 187932960252377831844147114439809453169994784359
  Found factor: 82139326753203199375875050117828431201
  Found factor: 92996380224197631797992554469814405893
  Found factor: 303179890235998775316115532875614603934123402931
  Found factor: 26447489051375929529673702839
  Found factor: 791253806472635792402241507385377445339970887312344156481
  Found factor: 67663508326650169421530609058997379513
  Found factor: 28146213398081595565981710323
  Found factor: 82609585018502469694506928886646373693
  Found factor: 13265593190364088381
  Found factor: 27995892717844244917142294627
  Found factor: 8424981395986037929
  Found factor: 618877006643547170219870845600337733048760418222073493417

 Time required to post-process: 55 ms 498 µs

sage: print(f"Found the following collection of factors:\n{factors}")
Found the following collection of factors:
{3095419463, 3322961963, 3293073263, 2721757583, 3122409359, 4248511859, 2572131767, 2274966587}
sage: print(f"Found the complete factorization: {factors.is_complete()}")
Found the complete factorization: True

Note that there are many optional parameters that can be passed to the above convenience function, and to the functions it in turn calls, allowing the simulation, sampling and post-processing to be tweaked in various ways. For further details, please see the source code documentation for the aforementioned functions.