Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
476 questions
4
votes
0
answers
280
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.9k
4
votes
0
answers
122
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.8k
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,094
3
votes
0
answers
131
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.9k
2
votes
0
answers
147
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,094
3
votes
2
answers
332
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?
...
- 30.1k
1
vote
1
answer
145
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
414
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
133
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)
- 63.9k
3
votes
1
answer
284
views
What is the ring $A_{\Gamma}$ in the Cohen-Lenstra Heuristics?
I understand the work in Cohen and Lenstra's paper that leads up to the heuristics themselves, where they count weighted averages of functions defined over isomorphism classes of $A$-modules, where $A$...
- 13k
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$.
...
CommunityBot
- 1
-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 ...
- 2,429
3
votes
0
answers
171
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 ...
7
votes
1
answer
382
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,590
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 ...
- 151k
1
vote
1
answer
153
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.9k
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
120
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 ...
- 2,429
11
votes
4
answers
944
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? ...
- 13k
8
votes
5
answers
4k
views
Computational number theory
I am interested in learning computational number theory and doing some computer experiments.
Which sort of number theory problems can be solved by using computers? For example, is it possible to ...
- 2,558
1
vote
2
answers
345
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:...
- 148k
16
votes
4
answers
25k
views
Is there an efficient algorithm for finding a square root modulo a prime power?
Cipolla's algorithm http://en.wikipedia.org/wiki/Cipolla's_algorithm is an efficient algorithm for finding a square root modulo a prime number. Is there an efficient algorithm for finding a square ...
4
votes
1
answer
283
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$.
...
- 30.1k
3
votes
1
answer
288
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$ ...
- 6,051
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 ...
- 208
9
votes
6
answers
4k
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
"...
- 2,753
2
votes
2
answers
257
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),...
- 39.9k
3
votes
0
answers
164
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
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 $...
- 109k
1
vote
1
answer
587
views
A quadrant of residues
Assume that following inequality holds $$\mathsf{w,x,y,z<AB,AC,AD,BC,BD,CD<ABC,ABD,ACD,BCD<wx,wy,wz,xy,xz,yz}$$ with $$\mathsf{gcd(A,B)=gcd(A,C)=gcd(A,D)=gcd(B,C)=gcd(B,D)=gcd(C,D)=1}$$
...
CommunityBot
- 1
6
votes
2
answers
461
views
Divisibility labeling on a boolean lattice and positive Euler totient
Let $B_n$ be the rank $n$ boolean lattice (i.e. the subset lattice of $\{1,2, \dots , n \}$). Let $\hat{0}$ and $\hat{1}$ be the minimum and the maximum of $B_n$. Let $f: B_n \to \mathbb{N}$ be a ...
2
votes
2
answers
281
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.9k
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 ...
1
vote
1
answer
256
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)
- 4,713
2
votes
1
answer
260
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: ...
- 54.2k
3
votes
0
answers
573
views
Complexity of $\mathsf{gcd}(a,b)\bmod N$
Given $a,b\in\Bbb N$ where each $a,b$ is $n$-bits, we can compute $\mathsf{gcd}(a,b)$ in $cn^{1+\epsilon}$ bit operations for some fixed $c\geq1$.
My query is given $N,a,b$ where $a,b$ is $n$-bits ...
CommunityBot
- 1
5
votes
0
answers
126
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,429
5
votes
2
answers
341
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
<...
- 25.7k
8
votes
0
answers
375
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,429
0
votes
0
answers
125
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}}{\...
- 105k
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 ...
- 109k
0
votes
0
answers
152
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,561
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 ...
- 13.2k
8
votes
1
answer
335
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
8
votes
3
answers
2k
views
Numerical evaluation of the Petersson product of elliptic modular forms
It is known how to compute the Fourier expansion of elliptic modular forms using modular symbols, and it is known how to get numerical evaluations of $L$-functions of various type ; it's possible to ...
- 101
6
votes
2
answers
698
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
- 30.5k
8
votes
0
answers
239
views
Computing the Moebius function $\mu$
Is it known whether computing $\mu(n)$ for a given integer $n$ is as hard as factorization?
- 20.2k
2
votes
1
answer
721
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 ...
- 5,382