This repository contains an artifact belonging to the paper
'Large smooth twins from short lattice vectors', by Erik Mulder, Bruno Sterner and Wessel van Woerden.
Available at arXiv.
The script in this repository allows to find smooth twins (r,r+1) where both r and r+1 are smooth, i.e., factor into small primes, using lattice techniques.
A dataset containing the conjectured complete set of
The indicated version has been tested. We expect the code to also work on later version.
- Python3 (3.12.3)
- Numpy (2.4.0)
- mpmath (1.3.0)
- General Sieve Kernel G6K, commit
c71e084dd003e1ffbfe8c91a7211b0ce9da22245.
The following additional dependencies might be required for G6K: libmpfr-dev, libgmp-dev, libmpc-dev and pkg-config.
On an apt-based system these can be installed by:
sudo apt install libmpfr-dev libgmp-dev libmpc-dev pkg-config
Then, install G6K inside script folder.
git clone https://github.com/fplll/g6k.git
cd g6k && PYTHON=python3 ./bootstrap.sh -j 4 && cd ../
If one already has G6K installed somewhere change the path on line 14 of experiment.py: sys.path.append('./g6k') to the appropriate value (and activate the g6k environment there).
Activate the G6K environment
source g6k/activate
Run script using default parameters and smoothness bound of 400.
python3 experiment.py 400
By default the script uses 4 cpu threads. This can be changed by passing --threads X.
The usage of the cli tool is explained by running python3 experiment.py -h which returns the following.
usage: experiment.py [-h] [-a LOG2A] [-k REMOVE] [-Q LEAVEOUT [LEAVEOUT ...]] [-eta DOWNSCALING] [-f FIRSTEXP] [-l LIFTDIMS] [-e DIAGEXP] [-t THREADS] B
positional arguments:
B Smoothness bound for the lattice sieve -- this is default to 400 unless changed
options:
-h, --help show this help message and exit
-a LOG2A, --log2a LOG2A
list of log₂(alpha) to try -- this is default to 128 unless changed
-k REMOVE, --remove REMOVE
number of primes to remove from P_B = { p < B } -- this is default to 0 unless changed
-Q LEAVEOUT [LEAVEOUT ...], --leaveout LEAVEOUT [LEAVEOUT ...]
explicit primes to remove from P_B = { p < B } -- don't use together with k
-eta DOWNSCALING, --downscaling DOWNSCALING
extra downscaling factors for prime 2 -- this is default to 1 unless changed
-f FIRSTEXP, --firstexp FIRSTEXP
exponents of first primes in factor basis -- this is default to 1 unless changed
-l LIFTDIMS, --liftdims LIFTDIMS
Number of dimensions for free used
-e DIAGEXP, --diagexp DIAGEXP
Exponent of log(p_i) on diagonal
-r REPEAT, --repeat REPEAT
Number of repetitions of run_instance -- this is default to 1 unless changed
-t THREADS, --threads THREADS
Number of cpu threads used for sieving -- this is default to 4 unless changed
We showcase some examples here demonstrating how the different parameters can be used. The lattice sieving process is inherently random so sometimes one has to rerun an example several times to obtain the claimed result.
With a smoothness bound of B=199, and log₂(alpha)=94 one can find the conjectured optimal twin r=22529735146513345759959448575 (eqn (9) in the paper).
python3 experiment.py 200 -a 94
For this case log₂(alpha_opt) = 96.32406.. and one indeed obtains a lower ratio nrm/gh for the above twin in this lattice.
python3 experiment.py 200 -a 96.32406
For B=350 and log₂(alpha) = 130 one can find the conjectured optimal 331-smooth twin r=405235055486365672469126661251479124999. This might require several runs as nrm/gh=1.150 is rather high.
python3 experiment.py 350 -a 130
By increasing the smoothness bound B relative to log₂(alpha) one can find multiple non-optimal twins.
python3 experiment.py 250 -a 94
python3 experiment.py 300 -a 110
python3 experiment.py 390 -a 104 # many solutions
Lifting can be used to limit the sieving dimension at the cost of potentially missing some twins. For example one can compare the following runs:
python3 experiment.py 400
python3 experiment.py 400 -l 5
python3 experiment.py 400 -l 10
The first two runs with l=0 and l=5 lifting dimensions typically find the conjectured optimal 397-smooth twin r=4851355181687302179614549844276285879489 with the latter being roughly twice as fast. The run with l=10 lifting dimensions can still find the same twin but might require several runs.
Lifting can also make it feasible to find larger heuristically optimal smooth twins, for example r=178906349213593152248817474720832242569815163684 with the following call:
python3 experiment.py 500 -a 158 -l 7 # takes 5-10 minutes
Some smooth twins cannot be found in the full lattice because their nrm/gh ratio is too large there. In this case guessing can help.
The option -Q can be used to leave out certain primes from the factor base. The following example allows to find the twin r = 12710981692278917870543664108164
python3 experiment.py 390 -a 104 -Q 107 113 131 139 149 151 157 163 179 211 223 269 271 277 307 331 337 349 367 379
with ratio nrm/gh = 1.148 while in the full lattice (with log₂(alpha)=104) this twin hasnrm/gh=1.27.
Another example is the twins r=10920928699070194316444991230220 and r=42463025494540282058195572890624 which can (sometimes) be found using the following guess:
python3 experiment.py 390 -a 104 -Q 163 181 191 197 229 233 239 263 271 293 307 311 317 373 379
As it is typically not clear which primes to leave out one can also leave out a random subset of size k.
python3 experiment.py 390 -a 104 -k 15
This will by default not remove the first 20 primes as those are more likely to divide a smooth integer.
Lifting and guessing can be combined to find smooth twins while sieving in much lower dimensions.
For example the 499-smooth twin r=178906349213593152248817474720832242569815163684 can be found (after several runs) with
python3 experiment.py 500 -a 158 -l 7 -Q 211 233 239 241 269 349 389 409 421 461
in which lattice it satisfies nrm/gh=0.924.
By scaling the weight on the prime 2 by a factor eta we can make it more likely to find a smooth twin with a large factor 2 in r(r+1).
For example for B=269, r=292471243019458753593343 with a factor 2^27 in r+1 can be found with:
python3 experiment.py 270 -a 80 -eta 5
For B=383, r=5385548235435185281171455 with a factor 2^35 in r+1 can be found with
python3 experiment.py 385 -a 83 -eta 5
For B=397, r=1674292053470895806082973695 with a factor 2^43 in r+1 can be found with
python3 experiment.py 400 -a 92 -eta 5
Lastly, for B=499, the twin r=5354730252078693477272904283665203199 with a factor 2^31 can be found with
python3 experiment.py 500 -a 123.5 -eta 10 -l 5 -Q 157 167 193 223 349 421
which gives the prime p=2*(r+1)^2 - 1 from the paper giving more efficient SQIsign1D parameters.
Alternatively, one can replace p₁ = 2 in the factor base with p₁ = 2^f which filters for smooth twins with 2^f | r(r+1).
For B=300, r = 2590056244138053909685469184 with a factor 2^19 in r can be found with
python3 experiment.py 300 -a 92.91 -f 19
Note that this could also be found with the eta parameter with (say) eta = 5. For some twins however, the eta parameter is not sufficient but combining with this f parameter can help. Take for instance
python3 experiment.py 390 -a 108.58851 -eta 5 -f 24
which finds r = 123522082404398462603335208796159.
We also include a script that heuristically estimates the largest B-smooth twin (in accordance with Section 3 of the paper). In addition to the Python3 dependency this also needs SageMath (primarily for using the Dickman - De Bruijn function).
- SageMath (10.5)
There are three inputs to this script which are explained by running sage twin_properties.sage -h.
> sage twin_properties.sage -h
positional arguments:
B Smoothness bound
options:
-h, --help show this help message and exit
-d DEC_PREC, --dec_prec DEC_PREC
decimal precision of the approximation -- this is default to 10 unless changed
-b BUPP, --bupp BUPP upper smoothness bound if its non-zero: will try all primes between B and this --bupp flag -- this
is default to 0 unless changed
For example to run this with B = 1250 execute the following:
sage twin_properties.sage 1250
which outputs log₂(largest B-smooth twin) = 255.9202330250.