Algorithms to Uniformly Generate Random Factored Smooth Integers
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909989977718784 |
|---|---|
| author | Bach, Eric Sorenson, Jonathan |
| author_facet | Bach, Eric Sorenson, Jonathan |
| contents | Let $x\ge y>0$ be integers. A positive integer is $y$-smooth if all its prime divisors are at most $y$. Let $Ψ(x,y)$ count the number of $y$-smooth integers up to $x$. We present several algorithms that will generate an integer $n\le x$ at random, with known prime factorization, such that $n$ is $y$-smooth. We begin by describing algorithms to compute $Ψ(x,y)$ exactly and to enumerate $y$-smooth integers up to $x$ in lexicographic order by prime divisor. Both of these are based on Buchstab's identity, and were likely known before. Then we present an algorithm that accepts as input a parameter $r$, $0\le r<1$, and returns the integer $n$ that is at position $\lfloor rΨ(x,y)\rfloor$ in the lexicographic ordering of all $y$-smooth integers up to $x$. Here position 0 is the first position. Thus, $n$ is generated uniformly so long as $r$ is chosen uniformly. This algorithm has a running time of $O(Ψ(x,y)\log\log y)$ arithmetic operations. We then explore the tradeoff between speed and rigor. By relaxing the uniformity of the output and allowing for multiple heuristics in our runtime analysis, we improve the running time to $$ O\left( \frac{ (\log x)^3 }{\log\log x} \right)$$ arithmetic operations. We conclude with a sample run by generating a $10000$-smooth integer $\le 10^{100}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2006_07445 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Algorithms to Uniformly Generate Random Factored Smooth Integers Bach, Eric Sorenson, Jonathan Number Theory 11y16, 11y05, 68q25 Let $x\ge y>0$ be integers. A positive integer is $y$-smooth if all its prime divisors are at most $y$. Let $Ψ(x,y)$ count the number of $y$-smooth integers up to $x$. We present several algorithms that will generate an integer $n\le x$ at random, with known prime factorization, such that $n$ is $y$-smooth. We begin by describing algorithms to compute $Ψ(x,y)$ exactly and to enumerate $y$-smooth integers up to $x$ in lexicographic order by prime divisor. Both of these are based on Buchstab's identity, and were likely known before. Then we present an algorithm that accepts as input a parameter $r$, $0\le r<1$, and returns the integer $n$ that is at position $\lfloor rΨ(x,y)\rfloor$ in the lexicographic ordering of all $y$-smooth integers up to $x$. Here position 0 is the first position. Thus, $n$ is generated uniformly so long as $r$ is chosen uniformly. This algorithm has a running time of $O(Ψ(x,y)\log\log y)$ arithmetic operations. We then explore the tradeoff between speed and rigor. By relaxing the uniformity of the output and allowing for multiple heuristics in our runtime analysis, we improve the running time to $$ O\left( \frac{ (\log x)^3 }{\log\log x} \right)$$ arithmetic operations. We conclude with a sample run by generating a $10000$-smooth integer $\le 10^{100}$. |
| title | Algorithms to Uniformly Generate Random Factored Smooth Integers |
| topic | Number Theory 11y16, 11y05, 68q25 |
| url | https://arxiv.org/abs/2006.07445 |