Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
476 questions
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
...
- 54.2k
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^{...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 $\...
- 6,039
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 ...
CommunityBot
- 1
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.)
...
CommunityBot
- 1
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 ...
- 39.9k
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 ...
- 6,397
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 ...
CommunityBot
- 1
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 ...
-1
votes
1
answer
1k
views
Transition Graph per alphabet? [closed]
How do you determine how many different Transition Graphs are over a particular alphabet? For example How many TG's are over the alphabet {x, y}. I am taking a class with a similar question from ...
CommunityBot
- 1
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 ...
- 619
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
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 ...
CommunityBot
- 1
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}}$$ ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
- 37k
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 ...
- 25.4k
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$ ...
CommunityBot
- 1
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 $\...
CommunityBot
- 1
15
votes
4
answers
2k
views
Computing minimal polynomials using LLL
I would like to use the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL algorithm) to compute the minimal polynomial of a (real) algebraic number $\alpha$ from a decimal approximation $a$...
CommunityBot
- 1
9
votes
2
answers
647
views
On bounds for idoneal integer
What is the best known lower bound and upper bound known for such a number if it exists and have there been any attempts (computational including) to eliminate the existence of such a number in known ...
CommunityBot
- 1
7
votes
1
answer
353
views
Numerically double-checking formula with L-values
I'm working with a special case of Ichino's triple product formula, which for classical holomorphic newforms $f$, $g$ ,$h$ of weights $k$, $m-k$, $m$ (and central characters satisfying $\chi_f \chi_g =...
CommunityBot
- 1
0
votes
1
answer
665
views
A three variable linear diophantine promise problem
Given $a,b,c,s\in\Bbb N$ such that $(a,b,c)=1$ with promise that we have at most one triple $x,y,z\in\Bbb N$ such that $ax+by+cz=s$, what is a good algorithm that runs in $O(\log(abcs))$ time to find ...
CommunityBot
- 1
3
votes
1
answer
456
views
On Pell's equation
A post was made (Reduction from factoring to solving Pell equation) seeking clarification to solving $$x^2-Dy^2=1$$ to factoring when $D>0$. An answer was posted stating that to factor $N$, it ...
CommunityBot
- 1
11
votes
1
answer
565
views
When adding a constant makes a multivariate polynomial reducible?
Given a multivariate polynomial $f(x_1,\dots,x_n)$ with integer coefficients, how to find an integer $m$ (if it exists) such that $f(x_1,\dots,x_n) + m$ factors into polynomials of smaller degrees?
...
- 22.5k
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{...
CommunityBot
- 1
6
votes
1
answer
412
views
Computing an eigencuspform in $S_2(\Gamma_0(1776))$
Consider
$$\bar{\rho}:G_{\mathbb Q}\longrightarrow\operatorname{GL}_2(\mathbb F_7)$$
the residual 7-adic Galois representation attached to the elliptic curve $y^2=x^3+x^2-4x-4$ of conductor 48. Then $...
- 37k
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{...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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
1
vote
1
answer
325
views
Error term for prime harmonic
What is known about the asymptotic behavior of
$$
f(x)=\sum_{p\le x}\frac1p-\log\log x-B_1?
$$
Of course by Mertens we know that $f(x)=o(1),$ but has more been proved (in terms of $O$ or $\Omega_\pm$,...
- 1,951
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 ...
CommunityBot
- 1
3
votes
1
answer
711
views
Residues and values of Riemann Zeta function at some points
I need the following computational results for proving something.
Let $1/2 + i\gamma_0$, be the first nontrivial zero of Riemann zeta function, $\zeta(s)$,
i.e. $\gamma_0\sim 14.134...$.
1) what is ...
- 897
27
votes
2
answers
2k
views
How to explicitly compute lifting of points from an elliptic curve to a modular curve?
Say $E$ is an elliptic curve over the rationals, of conductor $N$. There's a covering of $E$ by the modular curve $X_0(N)$, and if you rig it right then you can define this map over $\mathbf{Q}$: ...
CommunityBot
- 1
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
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$. ...
CommunityBot
- 1
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]$...
- 5
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
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 ...
CommunityBot
- 1
2
votes
1
answer
356
views
Computing all "suboptimal" rational approximations to $\pi/2$
I have an irrational number $\alpha$ ($\alpha=\frac\pi2$), and I would like to determine all integers $n\in[1,N]$ ($N=10^{16}$) that satisfy
$$ n \epsilon(n)^2 \leq \tau $$
where $\tau$ is a known ...
- 79.9k
2
votes
3
answers
476
views
How to define the input of computable function or Turing machine over real numbers
Computation or computability over $\mathbb{N}$ can be extended to computation or computability over $\mathbb{R}$ or even computation or computability over $\mathbb{C}$.The following is a formal ...
- 5,502
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
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 ...
- 54.2k
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 ...
CommunityBot
- 1
1
vote
2
answers
751
views
Computational complexity of solution of Pell equation and more
What is computational complexity for computing integral solution of Pell equation .It seems to be in P ,and could any one give an algorithm and reference for proof of it's complexity?
And more,could ...
- 24.8k
13
votes
3
answers
1k
views
Is there a composite number that satisfies these conditions?
We know that if $q=4k+3$ ($q$ is a prime), then $(a+bi)^q=a-bi \pmod q$ for every Gaussian integer $a+bi$. Now consider a composite number $N=4k+3$ that satisfies this condition for the case $a+bi=3+...
- 13