Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
477 questions
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$.
...
- 25.4k
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$ ...
- 131
18
votes
3
answers
562
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.
...
- 17.1k
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
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
"...
- 1,625
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),...
- 3,104
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
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
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: ...
- 1,561
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
1
vote
1
answer
257
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
342
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
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}}{\...
- 13.9k
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
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
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
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
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 ...
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
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
- 335
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
295
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
...
- 25.4k
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 ...
- 13.9k
1
vote
1
answer
183
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
69
votes
1
answer
4k
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 ...
- 34.4k
1
vote
1
answer
199
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,377
3
votes
1
answer
451
views
Finite group of units in quaternion orders
Let $F$ be a totally real number field, $R$ is a quaternion algebra over $F$ ramified in all infinite places of $F$. Let $\mathcal{O}\subset R$ be an order. By assumption on $R$ its group of units $\...
- 7,377
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 ...
5
votes
2
answers
314
views
Congruences for the non-divisors of Euler's $\phi(n)$
If $n$ is composite, then $\phi(n) < n-1$: hence, there is at least one number $d$ which does not divide $\phi(n)$ but divides$(n-1)$. We shall call $d$ the totient divisor of $n$. The purist will ...
- 5,470
6
votes
3
answers
559
views
Compute the kernel of multiplication of algebraic numbers
Let $\lambda_1, \dots, \lambda_n$ be the roots of a polynomial $g(x)$ of $n$-degree with rational coefficients and such that $g(0) \neq 0$. (Hence obviously they are non-zero algebraic numbers.)
...
- 502
1
vote
0
answers
152
views
Efficient deterministic algorithms of factorizing
My question is about efficient deterministic algorithms of factorizing polynomials of degree $n$ over $\mathbb{F}_q$.
Are there such algorithms that use poly$(n, \log q)$ bit operations?
I know ...
- 2,576
13
votes
1
answer
1k
views
An efficient isomorphism between finite fields
Let $p$ be a prime number. Let $f$ and $g$ be irreducible polynomials over $\mathbb{F}_p$, both of degree $n$. We know that factor-rings $\mathbb{F}_p[x]/(f)$ and $\mathbb{F}_p[x]/(g)$ are isomorphic ...
- 2,576
3
votes
0
answers
140
views
Structured factoring
Is it easier to factor $$(ax + b) (ay+ c)=M$$ where $a,b,c\in\Bbb N$ are known where $b$ and $c$ are similar in size and $a$ is approximately $b^{2/3}$ and unknowns $x,y\in\Bbb N$ and are ...
user76479
2
votes
2
answers
540
views
Algorithm for checking linear independence of algebraic numbers
Is there any if and only if condition for checking $\mathbb{Q}$-linear independence of given a set of numbers say $\alpha_i$ ? More precisely how to check linear independence of given $n$ algebraic ...
3
votes
1
answer
266
views
Calculating greatest common divisor series: $\gcd(1,x)+\gcd(2,x)+\gcd(3,x)+....+\gcd(x,x)$ [closed]
How to compute the value of $$[\gcd(1,x)+\gcd(2,x)+\gcd(3,x)+....+\gcd(x,x)]$$ efficiently?
When x can be as large as million.
- 33
5
votes
0
answers
741
views
Primitive element for a number field, and ramification
Let $K=\mathbb Q(\theta)$ be a number field with integral primitive element $\theta$, and let $f(x)$ be the minimal polynomial of $\theta$. Let $p$ be a rational prime. It's well known that if $p$ ...
- 1,021
2
votes
0
answers
116
views
Algorithm to generate random polynomials which has root in Q(a) where a is another algebraic number
Suppose you are given an algebraic number $\alpha$ . It is represented by $(p(x),(a,b),r)$ where $p(x)$ is its minimal polynomial. $a+ ib$ is an approximation of $\alpha$ such that there is no other ...
4
votes
1
answer
1k
views
Computing coefficients for the slash operator of a modular form
Suppose $f$ is a classical modular form of weight $r$ for a (congruence) group $\Gamma$. Let $\gamma$ be any matrix in $\operatorname{SL}_2(\mathbb{Z})$. Then the slash operator $|_\gamma$ is usually ...
- 295
1
vote
0
answers
106
views
parametrizing a conic in $F_p$ [closed]
Let $F_p$ be a finite field and $p\equiv 3 \pmod 4$, and $a,c$ are non-square elements in $F_p$.
I want to parametrize the conic:
$$cy^2=-3x^2-2ax-16a$$
($-1$ and $3$ are non-squares in this field ...
- 21
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 ...
- 13.9k
7
votes
0
answers
628
views
Proving Richardson's theorem for constants
(I asked this a little over 3 months ago on math.SE, and when I initially re-asked here, no one had responded there. $\:$ After I re-asked here, Eric Towers responded there, since I had forgotten to ...
user5810
4
votes
1
answer
459
views
On the mixed sum of three k-th powers
Let the set $S_k=\{\pm x^k \pm y^k \pm z^k \ \vert \ x,y,z \in \mathbb{Z} \}$.
Note that the signs are independently positive or negative.
First of all $S_2 = \mathbb{Z}$ because (see the answers ...
5
votes
1
answer
305
views
The limit of the following product? What is the closed form of the value?
Assume that $P_n$ is the $n$'th prime: Please help me solve the following $$\lim_{k\to\infty} {k}\prod_{n=1}^k \frac{P_{2n-1}}{P_{2n}}$$
I am not really sure quite where to start here as I am ...
user82419
11
votes
2
answers
1k
views
Why going to number fields in number field sieve help beat quadratic sieve?
To factor an $n$ bit integer number field sieve roughly takes $$e^{c{(\ln\ln n)^{\frac23}}({\ln n})^{\frac13}}$$ time while quadratic sieve takes $$e^{c{(\ln\ln n)^{\frac12}}({\ln n})^{\frac12}}$$ ...
user76479
10
votes
2
answers
624
views
Computing millions of coefficients of non self-dual modular forms
To test some conjectures made by some colleagues, I need to compute millions of coefficients of non self-dual modular forms, preferably in low weight (say 2 or 3). A form such as this.
For elliptic ...
- 361
3
votes
1
answer
382
views
Equivalence between Diffie Hellman and Discrete Log
For which non-trivial groups, do we know that the Diffie Hellman problem and the Discrete Log are equivalent?
Is there any group for which we suspect them to be different?
Could there be a finite ...
user76479
2
votes
0
answers
306
views
Avoiding Chinese Remainder Theorem
Given $k\in\Bbb N$ with $k<(\log_2N)^{\frac1\alpha}$ where $\alpha>2$ is fixed and $N$ being some integer such that $$N<\prod_{i=1}^k\pi_i^{a_i}$$ where $\pi_1,\pi_2,\dots,\pi_{k-1},\pi_k$ ...
user76479