Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
477 questions
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
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
6
votes
0
answers
448
views
Are there always at least *five* divisions?
@JosephO'Rourke asked a question about a Collatz like function related to primes:
$f(n) =
\begin{cases}
n^2 & \text{if} \;n \;\text{is prime} \\
\lfloor n/2 \rfloor & \text{if} \;n \;\text{...
- 1,375
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
11
votes
1
answer
360
views
Does this notion of pseudoprime relative to a matrix appear in the literature?
Let $M$ be a square matrix with integer entries. Then Fermat's little theorem for matrices holds:
$$\text{tr}(M^p) \equiv \text{tr}(M) \bmod p.$$
This follows by an examination of the action of the ...
- 118k
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
3
votes
1
answer
233
views
Calculating (n ^ fibonacci(k)) MOD m for a large value of k
The value of $k$ can be very large indeed (up to $10^{12}$). Is there an efficient way to calculate the output?
Edit : 'm' is a prime number.
2
votes
2
answers
510
views
On Cubic Non-Residues Modulo a Prime [closed]
What is a good test for identifying cubic non-residues/residues and higher power non-residues/residues modulo a prime $R$ in terms of computational complexity?
Given $M$ and $N$, is there a good way ...
- 13.9k
12
votes
3
answers
881
views
What does the computer suggest about the parity of p(n), for n in a fixed arithmetic progression?
Let p(n) be the number of partitions of n. A famous theorem of Euler allows one to compute
the parity of p(n) quickly for quite large n. In:
On the distribution of parity in the partition function, ...
- 5,422
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 ...
9
votes
2
answers
808
views
Complexity of Membership-Testing for finite abelian groups
Consider the following abelian-subgroup membership-testing problem.
Inputs:
A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with arbitrary-...
11
votes
1
answer
2k
views
Integer values of a rational function
Suppose we are given a rational function with numerator and denominator being polynomials with integer coefficients. Is there an efficient algorithm for finding all integers arguments at which the ...
- 34.4k
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 ...
1
vote
0
answers
415
views
Rings of algebraic integers as quotients of polynomial rings
The ring of integers $\mathcal{O}_K$ of a number field $K$ is always isomorphic to some ring of the form $\mathbb{Z}[x_1, ..., x_r]/\mathfrak{p}$, where $\mathfrak{p} \subset \mathbb{Z}[x_1, ..., x_r]$...
- 704
6
votes
1
answer
456
views
Solving equations in a subset of rational numbers
Let $S$ be a set of all positive rational numbers $x$ such that $2x^2 - 1$ is a square, excluding $x=1$.
I am interested in computing as many as possible solutions in $S$ to either the following ...
- 34.4k
5
votes
0
answers
153
views
On factorization algorithms for $\mathcal{O}[x]$
We know that $\mathsf{LLL}$ algorithm provides factorization procedure that runs in poly time for polynomials in $\Bbb Z[x]$ that are primitive.
What other rings $\mathcal{O}$ can we use instead of $\...
user76479
7
votes
2
answers
732
views
Explicit map for Scholz reflection principle
The question is about the specific case of reflection theorems (copied straight from Franz Lemmermeyer's "Class Groups of Dihedral Extensions"):
Let $k^+ = \mathbb{Q}(\sqrt{m})$ with $m\in \mathbb{...
- 4,593
7
votes
0
answers
294
views
On the ratio of Gilbreath sequences
Definitions: let $n \in \mathbb{N}_{>0} \cup \{ \infty \}$ and let $E_n$ be the set of sequences $(d_i)_{i=1}^n$ such that $d_1=1$, $d_i$ is an even integer (for $i > 1$) and $0<d_i \le i$. ...
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
12
votes
1
answer
869
views
Analytic lower bounds on the first sign change of pi(x) - li(x)?
There have been many results on the first sign change of $\pi(x)-{\mathrm{li}}(x)$: among others, Lehman, te Riele, Bays & Hudson, Demichael, Chao & Plymen, and most recently Saouter & ...
- 9,114
2
votes
1
answer
2k
views
How many cpus needed to check a 100 million digit prime number efficiently? [closed]
If I had access to potentially unlimited CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the mapped ...
- 123
1
vote
1
answer
353
views
Valid Difference Sets
Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as:
$$
d=p_i-p_j\mod N,\quad i\ne j
$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 0, 1, 2, ...
- 123
5
votes
1
answer
750
views
Effective bounds on Euler's totient
Quick question: It's known that
$$\limsup\frac{n}{\varphi(n)\log\log n}=e^\gamma$$
but are there known C and N such that
$$\varphi(n)>\frac{Cn}{e^\gamma\log\log n}$$
for all $n>N$?
Failing that,...
- 9,114
2
votes
2
answers
513
views
Unique representation of constructible numbers
I am interested in programmatically working with constructible numbers (the closure of the rational numbers under square roots). In order to perform comparisons between numbers I believe I would need ...
- 757
1
vote
1
answer
138
views
Runge-Kutta convergence [closed]
I am facing a problem solving a ODE with a Runge-Kutta 4th order method:
The expression in order to solve is :
\begin{equation}
Ay^{''}+By^{'}+Cy= Cu
\end{equation}
\begin{equation}
y =OUTPUT
\end{...
- 11
6
votes
2
answers
899
views
Enumerating representations of an integer as a sum of squares
Let $p$ be an odd prime. An old theorem of Jacobi asserts that $p$ has exactly $8(p+1)$ representations as a sum of four squares of integers (solutions counted with order and sign). What is the most ...
- 13.1k
2
votes
1
answer
387
views
Question on x coordinates of Mordell Curves where $y^2=x^3+k$ and $k^2 = 1$ mod $24$
In my ongoing search for Mordell curves of rank 8 and above I have currently identified 144,499 curves of a type where $k$ is squarefree and $k^2 = 1$ mod $24$.
In each case the x coordinates are ...
- 791
2
votes
0
answers
166
views
algorithm to find a new point of small height in a number field extension
By the height of an algebraic number $\alpha$, I mean the absolute, logarithmic (additive) Weil height $h(\alpha)$; e.g. $h(2^{1/n}) = (\log 2)/n.$
If $K$ is a number field, let $\delta(K)$ denote ...
- 1,499
2
votes
0
answers
769
views
Textbooks on Algorithmic Number Theory
I am looking for a good textbook suitable for graduate or advanced undergraduate students who want to explore algorithmic number theory. Specifically, algorithms for primality testing, and factoring ...
- 575
8
votes
2
answers
487
views
Efficient computation of the least fraction with square denominator greater than the square root of 2.
The least rational number greater than $\sqrt{2}$ that can be written as a ratio of integers $x/y$ with $y\le10^{100}$ can be found in a moment using a little Python program. Can anyone write a ...
- 6,209
3
votes
0
answers
203
views
Fourier expansions of newforms at width-1 cusps
Let $f_E$ be the newform attached to the Elliptic Curve $E$ with cremona label
$\textbf{100a1}$ and let $\alpha = \left[\begin{matrix} 1&0 \\ 10&1 \end{matrix}\right] \in SL_2(\mathbb{Z})$. ...
- 221
4
votes
0
answers
206
views
Monte Carlo variant of Hilbert's Tenth Problem
Let $k \in \mathbb{N}$. Given an algorithm $\mathcal{A}$ which takes
as argument a polynomial $P \in \mathbb{Z}[x_1,\dots,x_k]$ and either
returns true or false, we say that $\mathcal{A}$ works for $P$...
- 19.6k
1
vote
1
answer
1k
views
Computation for composition of polynomials
Let $R$ be a ring, $f(X)$ be a polynomial with coefficients in $R$ of degree $n$. It's known that for any $\alpha \in R$, one can evaluate $f$ at $\alpha$, i.e compute $f( \alpha) $ in $O(n)$ ...
- 1,109
9
votes
2
answers
756
views
Next (Restricted) B-Smooth Number Problem?
Given a bound, $B$, and a list of (small) primes $(p_0, p_1, \dots, p_{n-1})$ is there an efficient algorithm to find the next number greater than $B$ that can be expressed as a product of primes from ...
- 513
1
vote
3
answers
511
views
Differences of squares
Suppose I wanted to express a number $N$ as a difference of squares. For large $N$ this is in general difficult, as finding $N=a^2-b^2$ leads to the factorization $N=(a+b)(a-b)$. Even if the problem ...
- 9,114
3
votes
1
answer
427
views
Optimize / simple Set Covering Problem
Let $k,m\in\mathbb{N}$ be given. Let $M:=\{0,... , m-1\}$. How to find a subset $T\subset M$, $|T|=k$ such that $|T+T|$ is maximal, where $T+T=\{ (a+b)\mathbin\%m \mid a\in T,b\in T \}$ (“%” means ...
- 33
10
votes
3
answers
652
views
Computationally bounding a curve's genus from below?
Background
In the course of answering another question (Infinite collection of elements of a number field with very similar annihilating polynomials) I found myself with a curve, that if it had a ...
- 4,593
18
votes
0
answers
899
views
Computation of low weight Siegel modular forms
We have these huge tables of elliptic curves, which were generated by computing modular forms of weight $2$ and level $\Gamma_0(N)$ as N increased.
For abelian surfaces over $\mathbb{Q}$ we have very ...
- 41.4k
2
votes
1
answer
204
views
Is there a security analysis of the GQ digital signature scheme?
I'm doing summer cryptography research and I am have been looking for a security analysis of the Guillou-Quisquater (GQ) digital signature scheme, but I have been unable to find one.
Since this is not ...
- 1,441
4
votes
1
answer
354
views
Hejhal's algorithm and computational methods for non-classical Maass wave forms
Hejhal's algorithm [1] was a little gadget invented in the 90's for calculating the Hecke eigenvalues and Fourier coefficients of Maass wave forms. Later, Booker, Strombergsson, and Venkatesh (BSV) [2]...
- 309
8
votes
1
answer
716
views
Finding colinear points in F_q^n
Forgive me if this is well known, it's not really my field, but it's a problem I've run across and thought about a bit.
Let $\mathbb{F}_q$ be a finite field with $q$ elements, let $n\ge2$, and let $A,...
- 47.4k
3
votes
0
answers
172
views
Algorithm to compute a common denominator of a finite set of rational numbers
Let $x_1,\dots,x_n \in \mathbb{Q} \cap (0,1)$ be fixed, but unknown, and assume that we know a number $K \in \mathbb{N}$ such that there is a number $N \in \{1,\dots,K\}$ such that $x_1 N,\dots,x_n N \...
- 811
2
votes
0
answers
111
views
Comparing the size of two sums
Let $q$ be a prime power and $\mathbb{F}_q$ be the field of $q$ elements.
Let $\mathbb{F}_q[t]$ be the polynomial ring over $\mathbb{F}_q$.
I am working on a research project, where I bounded a ...
- 579
0
votes
1
answer
130
views
Size of approximate solution of an integer relation
Let $X_1$, ..., $X_n$ be a list of real numbers.
Consider an integer relation equation
$A_1 X_1 + \ldots + A_n X_n = 0$
where $A_1$, ..., $A_n$ are unknown integers.
Suppose somehow we are not so ...
- 1
0
votes
0
answers
461
views
Computational Ring Theory
I have tried to understand and program CGT algorithms though I am a beginner still. But I never get to hear Computational Ring Theory. Even GAP largely supports Groups Theory. Is there some initiative ...
- 133
1
vote
2
answers
337
views
Transformation of a bivariate polynomial into a homogeneous one
For a given a bivariate polynomial $P(x,y)$ with rational coefficients:
Q1. How compute such (invertible) substitutions of its variables that would transform the polynomial into a homogeneous one? In ...
- 34.4k
4
votes
2
answers
719
views
Computing index of a subgroup of SL_2 in sage
Suppose I have a subgroup of $\textrm{SL}_2(\mathbb Z)$ given by 3 generators, and it happens to be of finite index in $\textrm{SL}_2$. Is there a way (on Sage, since that is what I have access to) ...
- 315
2
votes
1
answer
121
views
Growth of the truncation of the integral multiples of an irrational number
Let $[a]$ denote the integral part of a real number $a$.
Let $a$ be an irrational number and $b$ a real number greater than $1$.
Consider the sequence $(b^n(na-[na]))$ with $n$ running on the ...
0
votes
1
answer
224
views
Spreading-out integers via multiplication
Let $a_1,...,a_n\in [0,m]$ be a set of $n$ positive integers, where $n<<m$, $m=poly(n)$.
One can assume $m$ is prime.
Is there an efficient, possibly randomized, way to find an integer $N=poly(n)...
- 445
4
votes
1
answer
390
views
Most orthogonal lattice basis
Let $n \in \mathbf{N}$ be a natural number and $v_1,\cdots,v_n$ a set of basis vectors in $\mathbb{R}^n$. How does one find the matrix $g \in \mathbf{GL}_n(\mathbb{Z})$ orthogonalizing these best ...
- 107