Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
477 questions
-5
votes
1
answer
178
views
Curious about methods for finding Goldbach pairs for large even numbers [closed]
I am exploring the question of efficiently identifying two prime numbers that sum to a given large even number, particularly for even numbers exceeding 100 digits. While brute force and precomputed ...
- 1
3
votes
1
answer
228
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 ...
- 111
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 $\...
1
vote
1
answer
242
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
-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
6
votes
1
answer
305
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
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 \...
- 661
0
votes
0
answers
79
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,101
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
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
14
votes
2
answers
685
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
35
votes
9
answers
9k
views
Why is integer factoring hard while determining whether an integer is prime easy?
In 2002, the discovery of the AKS algorithm proved that it is possible to determine whether an integer is prime in polynomial time deterministically. However, it is still not known whether there is an ...
- 2,649
5
votes
1
answer
203
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
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
2
votes
1
answer
159
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
93
votes
3
answers
6k
views
A little number theoretic game
I came up with this little two player game:
The players take turns naming a positive integer. When one player says the number $n$, the other player can only reply in two different ways: They can ...
- 861
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 ...
3
votes
1
answer
514
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
3
votes
1
answer
263
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 ...
- 27k
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
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
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
10
votes
2
answers
3k
views
Can every integer be written as a sum of squares of primes?
This question is mainly inspired from a different problem I was working on.
Is there a value of $k$ such that, for each $n\in \mathbb N$, the equation
$$\sum_{i=1}^{k}x_i^2=n$$
is solvable in $x_1,\...
- 791
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
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
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
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
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
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
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
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
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
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
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
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
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
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 ...
- 27k
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 ...
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
4
votes
1
answer
224
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
11
votes
2
answers
1k
views
Do consecutive integers have a big prime factor?
Let us say that three consecutive positive integers $(m-1,m,m+1)$ have a big prime factor if the largest prime factor $p$ of $N=(m-1)m(m+1)$ satisfies $e^p>N$.
I ckecked that it is true for all $m&...
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
1
vote
1
answer
107
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 ...
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)...
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
4
votes
2
answers
611
views
Ask for a generating function or an explicit expression of a triangle of positive integers
Preliminaries
I encountered the following triangle of positive integers:
$c_{n,k}$
$n=1$
$n=2$
$n=3$
$n=4$
$n=5$
$n=6$
$n=7$
$n=8$
$k=0$
$1$
$3$
$15$
$105$
$315$
$3465$
$45045$
$45045$
$k=1$
$5$
$...
- 1,101
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.6k