Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
448
questions
4
votes
0
answers
118
views
Finding short linear combinations in abelian groups
Let $M$ be a finitely generated abelian group. Assume we are given a presentation of $M$, that is
\begin{equation*}
M = \frac{\bigoplus_{i=1}^r \mathbf{Z}g_i}{\sum_{j=1}^s \mathbf{Z} r_j}
\end{...
- 20.5k
4
votes
0
answers
274
views
Parity of number of primes
In https://arxiv.org/abs/1009.3956 is it shown there is a $c>0$ such that $\pi(x)\bmod2$ can be computed in $o(x^{\frac12})$ time (more precisely number of primes $\bmod 2$ for an interval of ...
- 13.7k
0
votes
0
answers
74
views
Transformation or correspondence between language and real number
As we know, formal language can be regarded as a set of strings of alphabet, and real number can be regarded as sequence generated by set of integers, for example, denominators of the simple continued ...
- 3,000
2
votes
0
answers
143
views
Any proved connection between Roth theorem and hartmanis stearns conjecture?
Roth theorem classifies numbers into two classes, one is rational and transcendental, another is irrational algebraic numbers, by the number of solutions to the inequality (finite or infinite), and ...
- 3,000
3
votes
0
answers
128
views
Improving prime number generation probability?
Deterministic generation of primes in polynomial time is unknown.
Is there a way to probablistically in $O(n^c)$ time bound for some $c>0$ generate polynomially $\Omega(n^c)$ many integers in $[0,...
- 13.7k
3
votes
2
answers
318
views
On generating squarefree integers and primes?
Given an $\alpha\in(0,1)$ and $n\in\Bbb N$ what are some known deterministic algorithms to sample $O(n^\alpha)$ (not just get one) square free integers of $n$ bits? Is it $O(n^{\alpha})$ complexity?
...
- 13.7k
1
vote
1
answer
137
views
Estimate for de Bruijn function with small fixed smoothness bound
Let $\Psi(x,B)$ denote the number of $B$-smooth numbers less than $x$. Wikipedia gives the following "good estimate" for small, fixed $B$:
$$\Psi(x,B) \sim \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log ...
1
vote
0
answers
399
views
Norm to Principal Ideal
Over a number field, given the norm of an principal ideal, is there a way to find the principal ideal?
Also, Given ideals is there an algorithm to find principal ideals?
- 149
1
vote
0
answers
125
views
Finding Generators of an Ideal Over Number Field? [closed]
Is there any way or algorithm to find generators of an ideal over number field? (A algorithm that can be implemented and not expensive)
- 149
18
votes
1
answer
566
views
Complexity of a Fibonacci numbers discrete log variation
In my work I encountered the following
FIBMOD PROBLEM:
Given $k,m$ in binary, decide if there exists $n$ such that
$\, F_n = k \,$ (mod $m$). Here $F_n$ is a Fibonacci number.
This is a variation ...
- 16.3k
3
votes
0
answers
168
views
Scalar multiplication via the Kummer surface of a genus $2$ curve by $\sqrt{5}$
I hope this is a good question.
Recently I worked with genus two curves $H$ that have multiplication by $[\zeta_5]\in \text{Aut}(H)$, that is, multiplication by $e^{2\pi i/5}$. This automorphism is ...
6
votes
1
answer
324
views
Counting twin primes efficiently
This question, as well as its answers and comments, highlights a lot of unsettling numerical coincidences where certain sums over twin primes ostensibly converge to all kinds of weird values, however ...
- 5,380
48
votes
4
answers
3k
views
Twin primes conjecture and extrapolation method
Let $(p_1, p_2)$ be a twin prime pair, where we include $(2, 3)$. If $p_1 \equiv 1$ mod $4$ then we let $t_{(p_1, p_2)} := p_1 ^ 2 / p_2 ^ 2$ otherwise, we let $t_{(p_1, p_2)} := p_2 ^ 2 / p_1 ^ 2$.
...
- 1,305
1
vote
1
answer
152
views
Specializing non-trivial primality tests
Primes $p$ are integers with no factors (composite allowed) in $[1,p]$. There is a polynomial time test for them.
Given an interval $[a,b]$ what is the best way to test given integer $q$ has no ...
- 13.7k
1
vote
0
answers
94
views
How to encode a set of whole numbers $\{a_1,a_2,...,a_n\}$ such that given a number $x$ we can test if $x \in \{a_1,a_2,...,a_n\}$ [closed]
Suppose we have a set of whole numbers $\{a_1,a_2,...,a_n\}$. Is there a way to encode them into a new number $e$ such that we can use $e$ to test if a given number $x \in \{a_1,a_2,...,a_n\}$? So ...
- 111
2
votes
0
answers
118
views
Conjectures that can be tested with large numbers of Hecke eigenvalues of GSp(4) automorphic forms
As part of my thesis work I have proved Ibukiyama's conjecture implies something about $\mathrm{SO}(5)$ forms associated to certain lattices lifting to $\mathrm{GSp}(4)$ (This was originally a ...
11
votes
4
answers
3k
views
Computational complexity of finding the smallest number with n factors
Given $n \in \mathbb{N}$, suppose we seek the smallest number $f(n)$ with
at least $n$ distinct factors,
excluding $1$ and $n$.
For example, for $n=6$, $f(6)=24$,
because $24$ has the $6$ distinct ...
- 149k
11
votes
4
answers
932
views
How close can powers of coprime integers get?
Given coprime $a, b$, what is $$ \min_{x, y > 0} |a^x - b^y| $$
Here $x, y$ are integers. Obviously taking $x = y = 0$ gives an uninteresting answer; in general how close can these powers get? ...
- 1,703
1
vote
2
answers
313
views
Determining if a number is k-rough without factoring
A k-rough number is a natural number whose smallest prime factor is >= k, basically in opposition to the notion of a smooth number. Clearly, it's trivially easy to generate a k-rough composite number:...
- 379
2
votes
1
answer
397
views
How hard is it to compute these prime factor related problems?
We know that computing number of prime factors implies efficient factoring algorithm (How hard is it to compute the number of prime factors of a given integer?).
Let $\omega(n)$ be number of distinct ...
- 13.7k
-1
votes
1
answer
177
views
Solving quaternary quadratic forms modulo $q$ efficiently
Given a quaternary quadratic equation of form $$Q(a,b,c,d)=m$$ in $\Bbb Z[a,b,c,d]$ with coefficient sizes and $|m|$ bounded in magnitude by $B\in\Bbb N$ where $m\neq0$ if we are looking for solutions ...
- 13.7k
4
votes
1
answer
278
views
Small roots of $f(x) \equiv 0 \pmod{n^2}$
Let $f(x)$ be squarefree polynomial with integer coefficients.
For integer $n$ define "small root modulo $n^2$" integer $a$
satisfying $1 \le a \le n$ and $f(a) \equiv 0 \pmod{n^2}$ and
$f(a) \ne 0$.
...
- 24.2k
3
votes
1
answer
273
views
the size of a down-set?
I'm reading a research article lately, and got confused about a question.
So, the fundamental theorem of Kruskal and Katona states that if each set in a given set system $\mathcal{A}$ has $k$ ...
- 131
18
votes
3
answers
546
views
How to construct a small coprime?
Given an integer $n$, is there a deterministic algorithm to find in poly$(\log n)$ time an integer $q$, $n < q< n^{c}$, such that $gcd(q,n!)=1$? Here $c>1$ is some fixed constant.
...
- 16.3k
10
votes
3
answers
1k
views
Explicit formula for elementary symmetric sum
For $k\ge1$, $j\ge1$, Let $$e_k(j)=\sum_{1\le i_1<...<i_k\le j}i_1\cdot\cdot\cdot i_k.$$ We know that $e_k(j)$ is a polynomial in $j$ with coefficients depending on $k$. I am curious about ...
- 113
8
votes
6
answers
3k
views
Computation of a minimal polynomial
It is relatively easy (but sometimes quite cumbersome) to compute the minimal polynomial of an algebraic number $\alpha$ when $\alpha$ is expressible in radicals. For example, the simple query
"...
- 1,573
2
votes
2
answers
253
views
Reference request for function by which to compute coefficients of continued fraction of algebaic number
The simple continued fraction is in the form
$$[1;1,2,3,4,5,\dots]=1+\cfrac{1}{1+\cfrac{1}{2+\cdots}}, $$ for instance. Obviously,the coefficients $x_i$can be computed by computable function $x_i=f(i),...
- 3,000
3
votes
0
answers
163
views
Explicit roots in algebraic extention of Q with roots
Denis Bouhineau in "Solving Geometrical Constraint System Using CLP Based on Linear Constraint Solver" gave a method to find explicit square root in algebraic extention of Q with square roots. For ...
1
vote
1
answer
125
views
How do I find solutions of a quadratic Diophantine equation mod a large composite?
I'd like to find integral solutions to the equation
$2x^2 -3xy + y^2 \equiv 0 \mod n $
where $n$ is a given composite, for example, $n = 16807708473783470801$ (I prefer solutions that work for any $...
- 1,703
2
votes
0
answers
57
views
fast computation of cyclic totally real number fields of given degree and conductor
Let $n$ be an odd prime and $l$ also a prime s.t. $l\equiv1 \bmod n$. I want a fast way to compute the $n^{th}$ degree subextension of the $l^{th}$ cyclotomic field. I need to compute lots of these in ...
2
votes
1
answer
252
views
Fixed points of $g^x$ (modulo a prime)
In an explicit construction in combinatorics I need to study the following problem: assume we pick a odd prime number $p$, a generator $g$ of the multiplicative group $(Z/pZ)^{\ast}$.
Question 1: ...
- 1,543
5
votes
0
answers
125
views
Anyone got two Galois reps to compare?
I've got a new criterion for comparing Galois reps which are four dimensional if we know the kernel of the residual representation mod $5$ (or any large odd prime) and the Sato-Tate groups (should be ...
- 2,419
1
vote
1
answer
244
views
Lattice Sieving
What are some good references for Lattice Sieving in Number Field Sieve? Could someone suggest some research papers in this area?(Theoretical and Computational Perspective)
- 63
5
votes
2
answers
336
views
Methods to decide whether two positive definite ternary quadratic forms are in the same spinor genus?
Are there any effective methods to decide whether or not two positive definite ternary quadratic forms are in the same spinor genus?
For example, the following three forms are in the same genus
<...
8
votes
0
answers
371
views
Computing motivic Galois group
Suppose I have a motive $M$ over $\mathbb{Q}$, and can compute the Euler factor of the associated $L$-function for any good prime $p$. How can I compute the Zariski closure of the image of the Galois ...
- 2,419
0
votes
0
answers
123
views
Simultaneous Diophantine approximation in the non-generic case
Suppose we have $n$ irrational numbers $\{ x_1, x_2, \ldots, x_n \}$. For a generic set of such numbers, we have the well-known theorem that there exist infinitely many integers $q$ such that
$$ \...
- 265
1
vote
0
answers
168
views
$\mathsf{LLL}$ and linear diophantine equations
On page $8$ in these slides (http://www.math.unicaen.fr/~nitaj/LatticeMalaysia2014-2.pdf) it is told that if we want to solve $$x_1a_1+\dots+x_na_n=N$$ where $|x_i|<\frac{2^{n/4}N^\frac1{n+1}}{\...
- 13.7k
3
votes
0
answers
88
views
Current best time for factoring in $\Bbb Q[x]$
Lenstra Lenstra Lovasz have a $O((nb)^{11})$ deterministic algorithm to factor primitive polynomials in $\Bbb Q[x]$ where $b$ is total number of bits in the polynomial and $n$ is degree of the ...
user94040
0
votes
0
answers
150
views
Computer algebra programs for dummies [duplicate]
In the way of my investigations I have encounter the following computational problem: I have a system of 5 algebraic equations and I want to eliminate 4 of them. I also need to do a functional ...
- 1,543
2
votes
2
answers
279
views
On a number theoretic problem coming from multiuser coding?
Can Chinese remainder theorem be used to solve this problem in multiuser coding?
We have two transmitters sending integers $q,q'>0$ to a common receiver. The duty of the receiver is to recover ...
- 13.7k
5
votes
2
answers
1k
views
Is there a Bailey–Borwein–Plouffe (BBP) formula for e? [duplicate]
I recently used Bailey–Borwein–Plouffe formula to implement a π digit generator. Now I also want to implement an e digit generator, for the Euler number.
I've ...
user213
8
votes
1
answer
325
views
Existence of Randomized polynomial time algorithm and some arithmetic analog of $ACC^0$ circuits for Factoring of primitive polynomials before LLL?
Before LLL came along in $1982$ there was no deterministic polynomial (in degree and number of bits in coefficients) way to factor square free primitive polynomials in $\Bbb Z[x]$.
However was there ...
user94040
1
vote
0
answers
101
views
Two queries on irreducible factors without factoring - comparing integers and dense polynomials
Assume the polynomials here are dense.
In here it was asked the difficulty of counting prime factors of an integer.
We know for the cases of primitive polynomials in $\Bbb Z[x]$ and any polynomial ...
user94040
6
votes
2
answers
656
views
existence of an elliptic curves with given number of points over finite field
Is there a theorem which guarentees the existance of an elliptic curve with given number of points over $\mathbf{F}_p$ for a given $p$.
Thanks
- 335
8
votes
0
answers
235
views
Computing the Moebius function $\mu$
Is it known whether computing $\mu(n)$ for a given integer $n$ is as hard as factorization?
- 19.4k
2
votes
1
answer
288
views
Efficiently lifting $a^2+b^2 \equiv c^2 \pmod{n}$ to coprime integers
Let $n$ be integer with unknown factorization. Assume factoring $n$
is inefficient.
Let $a,b,c$ satisfy $a^2+b^2 \equiv c^2 \bmod{n}, 0 \le a,b,c \le n-1$.
Is it possibly to lift the above
...
- 24.2k
2
votes
1
answer
651
views
Complexity of $d$th root mod $n$
Supposing the product form $n=\prod_{i=1}^np_i^{e_i}$ is given with every prime $p_i$ and integer $e_i$ known and given $d\in\Bbb Z$ and $h\in\Bbb Z_n$ with $g^d=h\bmod p$ what is the complexity of ...
- 13.7k
1
vote
1
answer
182
views
On $a^{2t}+b^{2t}=1\bmod n$
For every $\epsilon\in(0,1)$ is there an $n_0\in\Bbb N$ such that at every $n\in\Bbb N_{>n_{0}}$ we can have coprime solutions $a,b$ (over $\Bbb Z$) such that $n^{\frac1{2t}+\epsilon}<a,b<2n^{...
user94040
68
votes
1
answer
3k
views
Iterations of $2^{n-1}+5$: the strong law of small numbers, or something bigger?
I've discovered what I believe is a quite remarkable sequence (A318970), defined by
$$n_1 = 3,\qquad n_{k+1} = 2^{n_k-1}+5\quad(k\geq 1).$$
Here are the first four terms with their prime ...
- 30.7k
1
vote
1
answer
188
views
Units in indefinite quaternionic algebra
This is the opposite to my last question case.
Let $F$ be a totally real number field, $R$ is a quaternion algebra over $F$ unramified in at least one infinite place of $F$. Let $\mathcal{O}⊂R$ be an ...
- 7,027