The computational-number-theo tag has no wiki summary.

**3**

votes

**0**answers

125 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 ...

**6**

votes

**0**answers

383 views

### Is formula valid for relating $\pi$ with ALL of its OEIS A002485(n)/A002486(n) convergents?

Could anyone try to prove that the below conjectured formula is valid for relating $\pi$ with ALL of its convergents - those, which are described in OEIS via A002485(n)/A002486(n) ?
$$(-1)^n\cdot(\pi ...

**2**

votes

**1**answer

101 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 ...

**1**

vote

**2**answers

236 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 ...

**0**

votes

**1**answer

100 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 ...

**3**

votes

**1**answer

185 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.

**1**

vote

**1**answer

231 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 ...

**1**

vote

**0**answers

73 views

### Is there any track for proving $D=NP$, besides showing that $D$ has polynomial-bounded universal quantifiers?

Background
By the MRDP theorem, every for every recursively enumerable set $S$, there exists a Diophantine polynomial $p$ such that
$$x \in S \iff \exists y_1, \dots, y_n \in \mathbb{N} \text{ such ...

**3**

votes

**2**answers

193 views

### Minkowski successive minima inequality for a lattice base?

Let $\Lambda$ be a lattice of $\mathbb{R}^n$, and $\lambda_i$ be the radius of the smallest ball containing $i$ linearly independent lattice vectors.
The Minkowski successive minima inequality says ...

**1**

vote

**1**answer

292 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, ...

**2**

votes

**1**answer

346 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 ...

**0**

votes

**1**answer

197 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 ...

**2**

votes

**2**answers

175 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 ...

**6**

votes

**3**answers

622 views

### Square Root Algorithm

I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?

**2**

votes

**0**answers

311 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 ...

**0**

votes

**0**answers

129 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 ...

**4**

votes

**2**answers

392 views

### Average involving the Euler phi function

Does
$$\frac{1}{N^2}\sum _{d=1}^N \log d \sum _{n=1}^{N/d} \frac{\phi(n)}{\log (dn)},$$
converges or not when $N$ goes to infinity?

**3**

votes

**1**answer

178 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) ...

**7**

votes

**0**answers

218 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?
...

**1**

vote

**2**answers

187 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 ...

**0**

votes

**2**answers

468 views

### On reducible polynomials with positive coefficients, $1$ as constant coefficient and certain bounds on coefficients

Given $a \in \mathbb{Z}$ with $a > 1$. Let $g(x) \in \mathbb{Z}[x]$ be a polynomial with $g(a)=\pm 1$. Let $h(x) \in \mathbb{Z}[x]$ be a polynomial with $h(a)= p$, a prime. Let $g(x)$ and $h(x)$ ...

**7**

votes

**1**answer

731 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, ...

**3**

votes

**0**answers

250 views

### Large numbers in small systems

Can we ever know the sum of the first $10^{10^{100}}$ digits of $\pi$?
Can we calgulate the $n$th digit of $\pi$ when the Kolmogorov-complexity of $n$ is larger than the complexity of the calculating ...

**12**

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 ...

**8**

votes

**3**answers

585 views

### Numerical evaluation of the Petersson product of elliptic modular forms

It is known how to compute the Fourier expansion of elliptic modular forms using modular symbols, and it is known how to get numerical evaluations of $L$-functions of various type ; it's possible to ...

**3**

votes

**3**answers

374 views

### Proving a least prime factor

Suppose that I find a small prime factor $p$ dividing a large number $n$ and I wish to prove that it is the least prime dividing $n$. There are two obvious approaches: either factor $n/p$, or divide ...

**6**

votes

**1**answer

340 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 ...

**1**

vote

**1**answer

165 views

### Counting modular squares in an interval

For an integer $m$, let $S^m_{x_0,x_1} = \{ t | x_0 â‰¤ t â‰¤ x_1 $ and $t$ is a square modulo $m \}$. Let $S^m_x$ = $S^m_{0,x}$.
Determining whether the sets $S^m_x$ are empty is easy (1 is always a ...

**2**

votes

**2**answers

499 views

### Integer partition and sum of squares

Hello,
The question below might be well known, and using different words (I made these up, I'm not a number theorist or specialist in combinatorics)
For all integers $n\geq 2$ denote by ...

**4**

votes

**1**answer

216 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 ...

**0**

votes

**1**answer

150 views

### Efficiency in deriving differences of divisor pairs

I have a computational problem where I need to derive the differences in divisor pairs in as few cpu cycles as possible.
In particular I am interested in divisors of numbers of the form ...

**5**

votes

**2**answers

504 views

### 12 descent scripts for pari/gp

I'm looking around for scripts to facilitate 12 descent on Mordell curves, preferably in Pari/gp.
I understand that Magma implements this feature, but unfortunately this software isn't available to ...

**8**

votes

**1**answer

269 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 ...

**11**

votes

**2**answers

673 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 ...

**8**

votes

**0**answers

507 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 ...

**0**

votes

**0**answers

95 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 ...

**3**

votes

**3**answers

585 views

### Computational number theory

Hello everybody!
I am interested in learning computational number theory and doing some computational experiments by computer!
I was wondering which sort of number theory problems can be solved by ...

**0**

votes

**2**answers

990 views

### Fibonacci Numbers Modulo m [closed]

In the paper "Fibonacci Series Modulo m" by D.D. Wall (found here), there is a table in the Appendix listing values for the function $k(p)$. This function is defined as the period of the Fibonacci ...

**0**

votes

**0**answers

96 views

### What is the largest computed summatory liouville interval ?

I am interested to know the largest computed summatory liouville interval, an implementation of which is detailed in Section 4.1 of [1].
The wikipedia page [2] for the function charts summatory ...

**1**

vote

**0**answers

163 views

### Efficient counting of Egyptian fractions with bounded denominators

I was amazed to discover that sequence http://oeis.org/A020473 in the OEIS has almost four hundred terms computed.
I wonder how one can get that far? E.g., how one can compute A020473(100)?
P.S. ...

**9**

votes

**3**answers

910 views

### Mertens' function in time $O(\sqrt x)$

This MathOverflow question seems to indicate that the state of the art in computing
$$
M(x)=\sum_{n\le x}\mu(n)
$$
takes time $\Theta(n^{2/3}(\log\log n)^{1/3}),$ which matches my understanding. ...

**15**

votes

**2**answers

944 views

### Sum of $\sum_{k=1}^nd(k^2)$

There is a literature dealing with
$$
\sum_{k\le x}d(f(k))
$$
where $f$ is an irreducible polynomial and $d(n)$ is the number of divisors of $n$. Erdos 1952 shows that the sum $\asymp x\log x,$ which ...

**11**

votes

**2**answers

647 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$ ...

**4**

votes

**2**answers

878 views

### Computing the fixed field of an automorphism of a function field

Let say we have a function field $k(x,y)$ defined by $f(x,y)$ over $k$, with $\sigma \in Aut(k(x,y)/k)$ and. Suppose, I'm not that out of luck, so that either of $\prod \sigma^i(x)$ or $\sum ...

**5**

votes

**2**answers

412 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 ...

**19**

votes

**1**answer

2k views

### How to calculate [10^10^10^10^10^-10^10]?

How to find an integer part of $10^{10^{10^{10^{10^{-10^{10}}}}}}$? It looks like it is slightly above $10^{10^{10}}$.

**1**

vote

**0**answers

335 views

### Witt rings and prime number generator?

Let $p$ be a fixed prime number. We define the ring of Witt vectors $W(R)$ for any commutative ring $R$ as follows:
For every ring morphism $R \rightarrow R'$ the induced morphism $W(R) \rightarrow ...

**4**

votes

**1**answer

277 views

### Hermit H-machines

I call an H-machine a machine that can be connected to turing machines and that takes as input a natural integer n and instantly returns the n'th digit of the mathematical constant H.
Is there a ...

**1**

vote

**0**answers

188 views

### Which rational subfields are corresponding to the two dimensional subspaces of holomorphic differentials

I implemented the algorithm that Felipe Voloch's suggested in his reply to the question:
Subfields of a function field
the algorithm is here:
Subfields of a function field
I considered the ...

**7**

votes

**3**answers

770 views

### Effective detection of CM modular forms

Say $f$ is a newform of weight $k$ and level $\Gamma_1(N)$. $f$ is called CM if, for example, there is an imaginary quadratic field $K$ such that for all $p\nmid N$ which are inert in $K$, the $p$th ...