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
0
answers
195
views
Is there some computational evidence of the $pq$ analog of Serre's conjecture?
The $pq$ analog of Serre's conjecture (see "Mod pq Galois representations and Serre's Conjecture"- Khare, Kiming) states that if $\bar{\rho}_1:G_{\mathbb{Q}}\rightarrow \text{GL}_2(\mathbb{F}_p)$ is a ...
user130124
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 $...
- 10.9k
2
votes
1
answer
228
views
A problem of divisibility
I came across the following problem. Find two integers, $u_{n}$ and $v_{n}$, such that
$$a_{n}=4u_{n}v_{n}+(6n-1)v_{n}+(6n-1)u_{n}+8n^{2}-4n$$
divides
$$b_{n}=-(2n-1)u_{n}v_{n}-(2n^{2}-3n)v_{n}-(2n^...
- 1,197
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 ...
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
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
346
views
approaching the border between absolute convergence and divergence of series
Let us consider absolute convergent series $\ell^{1^+}$ ordered under eventual dominance (mod finite) $<^*$. T. Bartoszynski proved that unbounded number ${\frak b}(\ell^{1^+}, <^*)$ equals ...
- 88
2
votes
0
answers
403
views
lower bounding the absolute value of a determinant
In a problem that I'm working on currently, the following question came up and I feel this should be fairly elementary, but I couldn't prove it myself/couldn't find a reference. Any pointers or ...
- 305
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 ...
user76479
1
vote
0
answers
123
views
Testing polynomials irreducible over the integers
Let $f\in\operatorname{int}(\mathbb Z)$, the ring of integer-valued rational polynomials. Define $\operatorname{P}^+(f)$ as the number of primes $>0$ that $f$ assumes at distinct integral arguments....
- 862
0
votes
1
answer
159
views
Parity and number of squares taken by polynomials in a range?
I have a polynomial $f(x)=a^2x^2+bx+c\in\mathbb Z[x]$ with $f(x)$ not a constant times a square and $abc\neq0$ and I want to know how many $x$ between $-a$ and $a$ the polynomial is a perfect square. ...
- 13.9k
0
votes
1
answer
120
views
How many integers $x$ satisfy that $x*p(x) \leq n$, where $p(x)$ means the largest prime factor of $x$?
I guess that the number of integers $x$ which satisfy the condition $x*p(x) \leq n$ is $O(n^{2/3})$ or $O(n^{3/4} / \ln n$), but I cannot prove it. I just write a program to count the number. The ...
- 611
1
vote
1
answer
153
views
Specializing non-trivial primality tests
Primes $p$ are integers with no factors (composite allowed) in $[1,p]$. There is a polynomial time test for them.
Given an interval $[a,b]$ what is the best way to test given integer $q$ has no ...
- 13.9k
4
votes
1
answer
254
views
Combinatorial computational problem about 0-1 vectors and sampling algorithms
Let $M \in \{0,1\}^{m\times n}$, where $n\gg 1$ and $m\le n$. A procedure consisting of the following three steps is repeated $t\gg 1$ times:
A row $\require{amsmath} \boldsymbol{r}$ of $M$ picked in ...
- 1,677
1
vote
1
answer
182
views
How many iterations the best biprime factoring method has to factor a number [closed]
I'm researching method of biprime number factoring. I have a biprime number 1012322327 * 1115382761 (19 decimal digits= 1129126872111204847). I'd like to know how many iterations (or trials) the best ...
- 113
2
votes
0
answers
127
views
Coppersmith's method to quadrivariate degree $2$ polynomials that behave as bivariate?
We have a polynomial $f(x_1,x_2,x_3,x_4)\in\mathbb Z[x_1,x_2,x_3,x_4]$ where the only monomials are either from set $$\{x_1,x_1x_2,x_2,x_3,x_3x_4,x_4\}$$ and we seek solutions $(x_1,x_2,x_3,x_4)\in\...
- 13.9k
15
votes
2
answers
1k
views
Saying things rapidly about integer factorisations
Let $N$ be a positive integer. Thanks to the Miller-Rabin test and the work of Agrawal, Kayal and Saxena, these days people have much much faster algorithms for testing whether $N$ is prime or ...
- 3,064
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}$: ...
- 41.4k
1
vote
0
answers
414
views
Norm to Principal Ideal
Over a number field, given the norm of an principal ideal, is there a way to find the principal ideal?
Also, Given ideals is there an algorithm to find principal ideals?
- 149
11
votes
2
answers
754
views
Interesting result on the Euler-Maschroni constant - what is the background?
Today I entered the following expression in maple:
$$a_i = H_{10^i} - ln(10^i) - \gamma$$
Here $H_j$ equals $\sum_{k=1}^{j} 1/k$ and $\gamma$ is the Euler-Mascheroni constant.
When I computed $a_n$ ...
- 397
2
votes
0
answers
78
views
Accelerating convergence of a product by multiplying by zeta values: history?
Let $R(s_1,\dotsc,s_n) = \prod_p r(p^{-s_1},\dotsc,p^{-s_n})$, where
$r$ is a rational function on $n$ variables. Say we want to compute the value of $R(s_1,\dotsc,s_n)$ for some choice of $s_1,\dotsc,...
- 545
3
votes
0
answers
186
views
Factoring problem similar to $RSA$ structure that is possibly not $NP$ complete and not $coNP$ also?
Standard factoring problem $\Pi_1$ is 'Given integers $N$ and $M$ is there a factor $d\in[1,M]$ of $N$?'. This is in $NP$ since such a factor is the witness and in $coNP$ since one can check all the ...
- 13.9k
0
votes
0
answers
83
views
Generating the digits in a base system by repeated multiplication of a number
The first 15 terms of the sequence {a_i} = 2^i are 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768. All of the digits in base-10, i.e. {0, ...
0
votes
1
answer
186
views
Could the sequence A287326 be generalized in order to receive expansion of natural power n>3? [closed]
The sequence https://oeis.org/A287326 - is Binomial distributed triangular array, that shows us necessary items to expand perfect cube $n^3$. Summation of $n$-th row of Triangle A287326 from $0$ to $n-...
- 167
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+...
- 131
3
votes
1
answer
284
views
What is the ring $A_{\Gamma}$ in the Cohen-Lenstra Heuristics?
I understand the work in Cohen and Lenstra's paper that leads up to the heuristics themselves, where they count weighted averages of functions defined over isomorphism classes of $A$-modules, where $A$...
- 179
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
4
votes
0
answers
281
views
Parity of number of primes
In https://arxiv.org/abs/1009.3956 is it shown there is a $c>0$ such that $\pi(x)\bmod2$ can be computed in $o(x^{\frac12})$ time (more precisely number of primes $\bmod 2$ for an interval of ...
- 13.9k
1
vote
1
answer
323
views
Number of biquadrates mod n
Is there an explicit formula for the number of fourth powers mod n?
Finch & Sebah [1] give theorems, partially folklore, for squares and cubes mod n, but I don't know of a similar formula for ...
- 9,114
8
votes
1
answer
1k
views
Recent Fast Multiplication Algorithms for Large Integers
The STOC 2008 paper "Fast Integer Multiplication using Modular Arithmetic" by De et al
http://arxiv.org/abs/0801.1416 shows how to use $p$-adic numbers instead of $\mathbb C$ used in Furer's ...
- 341
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
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
0
votes
0
answers
257
views
Hercules and the Hydra with time constraints
The game of Hercules vs. the Hydra can be put in terms of a single number in hereditarily-factorized form. For example, if the Hydra is $2^{19^3} \cdot 5^{11^7}$, Hercules must choose between two ...
- 2,302
15
votes
3
answers
3k
views
Finding zeroes of classical modular forms
There are several papers which compute zeroes of modular forms for genus 0 congruence subgroups, such as "Zeros of some level 2 Eisenstein series" by Garthwaite et al published in Proc AMS and work of ...
- 419
-1
votes
1
answer
177
views
Solving quaternary quadratic forms modulo $q$ efficiently
Given a quaternary quadratic equation of form $$Q(a,b,c,d)=m$$ in $\Bbb Z[a,b,c,d]$ with coefficient sizes and $|m|$ bounded in magnitude by $B\in\Bbb N$ where $m\neq0$ if we are looking for solutions ...
- 13.9k
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
8
votes
1
answer
1k
views
Can a Hamkins infinite time Turing Machine with infinite Super Turing jumps (from higher type oracles) get the power to decide $\Sigma_1^2$ sets?
Hamkins showed that his infinite time Turing machine has the power to decide some $\Delta_2^1$ sets. I wonder if some modifications of the machine could be made to reach level $\Sigma_1^2$ sets, or, ...
- 297
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
132
views
Quick computation of a certain exponential sum
Is there a quick way to compute (somewhat accurately) for large $X$, the following exponential sum, where $\Lambda$ is the von Mangoldt function?
$$\int_0^1 \bigg|\sum_{n\le X} \Lambda(n)e(n\alpha)\...
- 1,890
0
votes
0
answers
58
views
Quadrics over the univariate function field with discriminant of minimal degree
Consider a non-degenerate quadric $Q(x,y,z) \subset \mathrm{P}^2$ over the univariate function field $\mathbb{F}_p(t)$, where $\mathbb{F}_p$ is a prime finite field, $p > 2$. For simplicity assume ...
- 1,833
1
vote
1
answer
145
views
Estimate for de Bruijn function with small fixed smoothness bound
Let $\Psi(x,B)$ denote the number of $B$-smooth numbers less than $x$. Wikipedia gives the following "good estimate" for small, fixed $B$:
$$\Psi(x,B) \sim \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log ...
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
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
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
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
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
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
3
votes
0
answers
171
views
Scalar multiplication via the Kummer surface of a genus $2$ curve by $\sqrt{5}$
I hope this is a good question.
Recently I worked with genus two curves $H$ that have multiplication by $[\zeta_5]\in \text{Aut}(H)$, that is, multiplication by $e^{2\pi i/5}$. This automorphism is ...
2
votes
2
answers
413
views
Number Field Sieve for factorization with non-monic non-linear polynomial. Can't understand calculating ideal valuations
There is a paper "Factoring integers with the number field sieve" (download it here, for example).
I can't understand how they reason the correctness of computing ideal valuations in the case of ...
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