Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
49 questions from the last 365 days
0
votes
0
answers
61
views
Is the new method used by the GIMPS project applicable to non-Mersenne primes?
For years, there was a simple reason why the largest known prime is of the form $2^{p}-1$: We had the Lucas-Lehmer test which was specific to Mersenne numbers, and faster than all other known methods.
...
- 233
1
vote
0
answers
116
views
Can all congruences for a third-order recurrence relation hold for some composite $n$?
Let $p$ be a prime with $p \gt 3$. Consider the polynomial $f = x^3 - 3x -1$. Suppose $f$ is irreducible over $\mathbb{F}_{p}$. Let $E$ be the splitting field of $f$ over $\mathbb{F}_{p}$, and let $\...
2
votes
0
answers
161
views
Compute generators for group of totally positive units of a number field?
Given a number field $K$, I would like to compute (in Sage) generators for the group of totally positive units of $K$.
Update: I've tried some code (details below), which I've received some help on in ...
- 101
-1
votes
0
answers
73
views
Analog of ceil and floor of $\sqrt{a(a+1)}$ in modular arithmetic
If we take ceil and floor of $\sqrt{x(x+1)}$ (when it exists) we get $x$ and $x+1$ respectively. Is there an analog of this assuming roots exist in modular arithmetic (at least modulo primes)?
...
- 13.9k
0
votes
0
answers
78
views
Factoring totient of a prime
Is it any easy to factor $p-1$ when $p$ is a prime compared to general factorization problem?
What about when $2p+1$ is also a prime?
- 13.9k
1
vote
1
answer
240
views
The equation $ax^2 +by^2 =1 \mod P$ in cyclotomic field
Let $L$ be a cyclotomic field, and $P$ a prime ideal of $\mathcal{O}_L$.
is there any symbol for the equation $ax^2 + by^2 =1 \mod P$ and if so, is it computable in polynomial time?
if $a$ is ...
- 133
6
votes
1
answer
303
views
New Mersenne prime and compute time [closed]
GIMPS has just announced that $2^{136,279,841}-1$ is prime. Does anyone have a sense of the scale of the computational resources involved in finding this? (And maybe how it compares to, say, ...
- 133
0
votes
0
answers
78
views
Is there an asymptotic expansion for the reciprocal of the classical Euler beta function?
The classical Euler beta function can be defined by
$$
B(p,q)=\int_0^1t^{p-1}(1-t)^{q-1}\operatorname{d\!}t
$$
for $\Re(p),\Re(q)>0$.
The beta function and the classical Euler gamma function $\...
- 1,091
1
vote
0
answers
114
views
Simultaneous elimination of variables in multiple polynomials
I have a system of $n=O(1)$ non-homogeneous polynomials of total degree $d=O(1)$ $p_1,\dots,p_r\in \mathbb Z[x_1,\dots,x_n]$. I would like to eliminate $n-1$ variables simultaneously from the $n$ ...
- 13.9k
3
votes
1
answer
203
views
Chowla's theorem on class number of real quadratic field
Let $p\equiv1\bmod 4$ be a prime number and $h$
the class number of real quadratic field $\mathbb Q(\sqrt{p})$, $\epsilon=\frac{t+u\sqrt{p}}{2}$ its fundamental unit. In this paper https://www.pnas....
- 287
34
votes
0
answers
1k
views
Is $2\uparrow\uparrow\infty + 3$ divisible by a prime number?
Define power tower using Knuth's arrow: $$a\uparrow\uparrow b=\left.a^{a^{a^{...^a}}}\right\}b\text{ layers}$$
It can be proved that for any positive integers $a, n, m\ \ $,
$\lim_{n \to \infty} a \...
- 631
1
vote
0
answers
62
views
A conjecture on members of Lucas sequences not being pseudoprimes
Following conjecture on an infinite set of numbers satisfying the PSW-conjecture might be of academic interest in the understanding thereof.
Would you have any pointers on how to prove or disprove ...
2
votes
1
answer
157
views
$f(x)\bmod p$ and decomposition of prime ideals
While reading Serre's beautiful book Lectures on $N_X(p)$, I thought of a related question.
Let $f(x)\in \mathbb{Z}[x]$ be a monic irreducible polynomial with integer coefficients. Let $K$ be the ...
- 709
5
votes
1
answer
303
views
Efficiently computing $\prod_{i=1}^{n} A_i$
Let $k$ be a nonnegative integer, how to compute $\prod\limits_{i=1}^{n} A_i$ quickly and accurately, where $$A_i=\begin{bmatrix}
0 & 1\\
i^k & 1
\end{bmatrix}?$$
I know if $k=0$, we can use ...
- 696
3
votes
1
answer
513
views
Regarding the digit expansion of $\sqrt 7$
Let $\sqrt 7=\sum_{i=0}^\infty a_i 7^{-i}, 0\le a_i \le 6$ be the expansion of $\sqrt 7$ in base $7$.
I am curious about the following question: Is there a $K\in \mathbb{N}$ such that for any $n\ge ...
- 31
5
votes
0
answers
141
views
Compute weight of modular form from its Fourier coefficients
It is known that Hecke eigenform $f \in S_{k}(\Gamma_0(N), \chi)$ is uniquely determined by first $C_{k,N}$ many Fourier coefficients, where $C_{k,N}$ is a constant only depends on $k$ and $N$. For ...
- 2,215
2
votes
1
answer
108
views
On square root modulo $2^t-1$
Is there a way to compute an $x$ satisfying $$x^2\equiv a\bmod(2^t-1)$$ where $a,t$ are integers given to us and factorization of $2^t-1$ is not given to us?
- 13.9k
5
votes
1
answer
172
views
Isogenous elliptic curves and canonical modular polynomials
Let $\ell$ and $p$ be two primes. We are looking for a method for checking whether two supersingular elliptic curves over the finite field $F_p$, given through their $j$-invariants, are $\ell$-...
- 81
2
votes
0
answers
54
views
Conductor of hyperelliptic curve after adding a rational root
Let $r\geq 5$ be a prime. Suppose I have a specified hyperelliptic curve $C: y^2=f(x)$ defined over $\mathbb{Q}$, where $f\in\mathbb{Q}[x]$ has degree $r$.
Note: the roots of $f$ are not rational but ...
- 83
14
votes
2
answers
683
views
Can four integer numbers $x$, $y$, $x-y$, $x+y$ be powerful numbers where $\gcd(x,y)=1$?
Can four integer numbers $x$, $y$, $x-y$, $x+y$ be powerful numbers where $\gcd(x,y)=1$ ?
- 1,776
3
votes
1
answer
261
views
Could efficient solutions of $x^2+n y^2=A$ be related to integer factorization?
Let $n$ be positive integer with unknown factorization and $A$ integer with known
factorization.
According to pari/gp developers pari can efficiently find all solutions of:
$$x^2+n y^2=A \qquad (1)$$
...
- 25.4k
3
votes
3
answers
293
views
Finding a prime which is a square modulo all small primes
I want to find a small prime $p$ satisfying
$p\equiv 1 \pmod{8}$
$\left(\frac{p}{q} \right) = 1$ for all primes $3 \leq q \leq N$
where $N$ is a moderately large number (say, around $15,000$). I ...
- 26.9k
2
votes
0
answers
52
views
Conductor of hyperelliptic curve after base change
Let $r\geq 5$ be a prime, and let $\zeta$ denote a primitive
$r$-th root of unity. Let $C$ be a hyperelliptic curve defined over $\mathbb{Q}$.
Suppose I have computed the conductor exponent $n$ of $C/\...
- 83
2
votes
0
answers
107
views
Record for determining complete list of imaginary quadratic fields with small class number
In 2003, Mark Watkins (Class numbers of imaginary quadratic fields) determined all imaginary quadratic fields having class number at most 100.
Has this list been improved? That is, what is the largest ...
- 26.9k
2
votes
0
answers
146
views
Reference for accelerated sum to compute the Meissel-Mertens constant
The Meissel-Mertens constant
$$ B_1 = \lim_{n \to \infty} \left(\sum_{p \leq n} \frac{1}{p} - \log\log n\right) $$
has the series representation
$$
\begin{equation} \tag{1}
B_1 = \gamma + \sum_{n=2}^{...
- 451
0
votes
0
answers
61
views
Is generating semirandom blake256 hashes until packed points is on the curve, a safe algorithm to avoid the discrete log between the generated points?
I know there are more robust methods, but I wanted to know about this specific one
For any distinct said randomly generated point : $P_i,P_j\in \{P_1,...,P_k\}$ it should be hard to find $s$ such that ...
- 87
2
votes
0
answers
119
views
gcrd and associates of an element of the quaternion algebra over a totally real number field $K$
Let $K$ be a totally real number field of class number 1, and $Q$ the quaternion algebra over the ring of integers of $K$ with basis
$\{1,i,j,k\}$ such that $i^2 = j^2 = k^2 = -1$ and $ij = -ji, ik = ...
- 133
5
votes
0
answers
187
views
Is there an effective way to compute the square root of an algebraic number?
For an algebraic number $\alpha$, let $f_\alpha$ denote its minimal polynomial. We can symbolically represent an algebraic number $\alpha$ by the tuple
$$
(f_\alpha, x, y, r) \in \mathbb{Q}[x] \times ...
- 1,087
2
votes
0
answers
187
views
How to construct an explicit isomorphism of the split Quaternion Algebra $(a,b)_F$ over the field $F$ to $\mathrm{Mat}_2(F)$
$\DeclareMathOperator\Mat{Mat}$How to construct an explicit isomorphism of the split quaternion algebra $(a,b)_F$ over the field $F$ to $\Mat_2(F)$?
As it is known that the algebra of quaternions is ...
- 21
5
votes
2
answers
331
views
Computing the Abelian invariants of a subgroup of a f.g. Abelian group
We have a f.g. Abelian group $A$ given as a direct sum of $N$ cyclic subgroups $C_{k_j}=\langle x_j\rangle$, with $k_j\in \{2,\dots,\infty\}$, $1\leq j \leq N$, and the associated homomorphism $\phi:\...
- 14k
4
votes
0
answers
821
views
One of the numbers $\zeta(5), \zeta(7), \zeta(9), \zeta(11)$ is irrational
I am reading an interesting paper One of the numbers ζ(5), ζ(7), ζ(9), ζ(11) is irrational by Zudilin. We fix odd numbers $q$ and $r$, $q\geq r+4$ and a tuple $\eta_0,\eta_1,...,\eta_q$ of positive ...
- 11
1
vote
1
answer
73
views
Time complexity of Magma's `NormEquation` for quadratic extensions of $2$-adic fields
Note: This is similar to, but easier than, a previous question I asked here. It is a different question! I'm hoping this one might get an answer because it concerns a standard algorithm, whereas the ...
- 411
16
votes
2
answers
1k
views
Is it decidable whether two real algebraic irrationals generate the same extension of the rationals?
For an algebraic number $\alpha$, let $f_\alpha$ denote its minimal polynomial. We can symbolically represent an algebraic number $\alpha$ by the tuple
$$
(f_\alpha, x, y, r) \in \mathbb{Q}[x] \times ...
- 1,087
2
votes
1
answer
158
views
Are the coefficients in the stationary phase approximation computed explicitly somewhere
In Stein's "Harmonic analysis" book, page 334, one can find
the asymptotic expansion
An instructive proof is given for the case $k=2$. It is clear enough to generalize to the cases $k\geq ...
- 852
2
votes
2
answers
1k
views
Sum of three square is a square and sum of their product taken two at a time is also a square
Let $a^2 + b^2 + c^2 = X^2$ and
$$(ab)^2 + (ac)^2 + (bc)^2 = Y^2$$
Such that $a,b,c,x,y$ are all non zero Integers.
How to find All solutions ?
Is there any parametrization which gives Infinitely ...
- 147
1
vote
1
answer
106
views
Number of solutions for linear modular equations given GCD
We are currently investigating a problem involving number theory, an area outside our field of expertise.
Let $n$ be a positive integer. Consider two pairs of integers $(j,k)$ and $(j′,k′)$ as ...
13
votes
2
answers
1k
views
Using the Eichler-Selberg Trace formula to compute class numbers?
The Eichler-Selberg trace formula (Theorem 2.2 here) gives a relation between the trace of a Hecke operator acting on the space of cusp forms and sums of weighted class numbers of imaginary quadratic ...
- 133
4
votes
0
answers
66
views
Computing preimage of element under norm map of quadratic extension of $2$-adic fields
Let $F$ be a $2$-adic field, i.e. a finite extension of the $2$-adic numbers $\mathbb{Q}_2$. Suppose that I have a quadratic extension $E = F(\sqrt{d})$ of $F$. Given a unit $\alpha \in \mathcal{O}_F^\...
- 411
4
votes
1
answer
222
views
Generators of the ideal class group
Theorem 4 of Eric Bach's "Explicit bounds for primality testing and related problems" states the following:
Let $K$ be a number field of degree greater than 1. Let $d$ be the absolute value ...
- 43
6
votes
0
answers
200
views
Empirical bounds on $\left|\frac{\zeta'(1+it)}{\zeta(1+it)}\right|$
It is reasonable to expect that $$\left|\frac{\zeta'(1+it)}{\zeta(1+it)}\right| < 2 \log \log t$$
for all $t\geq 4$ (say): a somewhat stronger bound is known for $t\geq 10^{165}$ or so (Theorem 5 ...
- 20.2k
4
votes
0
answers
326
views
Are there infinitely many simple integral fusion rings of rank $4$?
$\DeclareMathOperator\ch{ch}$$\DeclareMathOperator\FPdim{FPdim}$We refer to [EGNO15, Chapter 3] for the notion of fusion ring and basic results. The type of a fusion ring $R$ is the list $(\FPdim(b_i)...
1
vote
2
answers
383
views
Is there any way to estimate this functions: $f(n)=\sum_{d|n}d\varphi(d)$ and $g(n)=\sum_{d|n}\frac{\varphi(d)}{d}$?
Let that $n$ be a natural number and $\varphi(n)$ be the Euler totient function. Is there any formula or estimation for computing functions $f,g$ such that:
$$
f(n)=\sum_{d\mid n}d\varphi(d)
$$
and
$$
...
- 139
3
votes
2
answers
287
views
When I know the two points on an elliptic curve, and the two points satisfy the relationship: $Q=e \cdot P$, is it possible for me to solve for e [closed]
When I know the two points on an elliptic curve, and the two points satisfy the relationship: $Q=e \cdot P$, is it possible for me to solve for $e$.
The equation of the curve is: $y^2 = x^3 + ax + b \...
- 31
0
votes
1
answer
126
views
Integer quadratic representation subject to discriminant minimization algorithm
Let $f(x)=ax^2+bx+c$ and $f(x)=n$. Is there an algorithm to choose $a,b,c$ such that the discriminant is minimized? Where $a,b,c,n,x$ are all integers.
More concretely, is there an algorithm to find $...
0
votes
0
answers
64
views
What is the lattice point distribution over binary quadratic forms?
Let $f(x,y)=x^2+ny^2$ be the binary quadratic form of interest and consider the lattice points $S=\{ (x,y,f(x,y)) \in \mathbb{N}^3 \}$.
For simplicity, we keep things only on quadrant I of the ...
5
votes
3
answers
366
views
How to recover integer part from known fractional root part?
Suppose you have $r=n+f$ where $n\in\mathbb{N}$ and $f\in (0,1)$. I know that $r^2$ is an integer and I can also get as many digits of $f$ as I like, is there a way to recover the value of $n$?
Thank ...
3
votes
1
answer
296
views
Does this condition characterise intervals, among subsets of the real line?
For a real number, $c\in \left]0,1\right[$, consider the following property $\mathbf(\mathbf P_c\mathbf)$ of subsets $A$ of $\mathbb R$:
$\mathbf(\mathbf P_c\mathbf)$ For every bounded set $B\subset \...
- 60.5k
1
vote
1
answer
207
views
Calculating the value of periodic continued fractions with $a_i\in\lbrace 0,1\rbrace$
Question:
How can the value of continued fractions of the form
$$y:=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{\begin{align}\ddots& \\ &a_{n-1}+\cfrac{1}{a_n+y}\end{align}}}}}$$
$$...
- 13.2k
2
votes
0
answers
71
views
Simultaneous computation of the three Weber modular functions
Recall that the three classical Weber modular functions are defined by
$f(\tau)=e^{-\pi i/24}\eta((\tau+1)/2)/\eta(\tau)$,
$f_1(\tau)=\eta(\tau/2)/\eta(\tau)$, and
$f_2(\tau)=\sqrt{2}\eta(2\tau)/\eta(\...
- 13.1k