# Tagged Questions

**4**

votes

**2**answers

341 views

### Are there any patterns in simple continued fraction expansions of algebraic real numbers?

As we know there are patterns in simple continued fraction expansion of quadratic algebraic numbers,are there any patterns in simple continued fraction expansions of other algebraic real ...

**3**

votes

**0**answers

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

**7**

votes

**1**answer

525 views

### Can the Legendre symbol be calculated in polynomial time?

Is there an algorithm which on input "$(a,p)$" (where $0\leq a<p$ are integers) takes time polynomial in $\log p$ and outputs "NOT PRIME" if $p$ is not prime and otherwise outputs the Legendre ...

**3**

votes

**2**answers

126 views

### All Integers from the Smallest Digit Stream with a Window Filter

Let's represent integers with D digits where each digit has B values
(i.e., the base is B and we effectively work only with integers between
1 and B^D). Is it possible to choose a single ...

**35**

votes

**1**answer

1k views

### improving known bounds for Pierce expansions; cash prize

Here's a problem that I thought of back in 1978 or so, and only a little progress has been made on it since then. I still think about it from time to time, but probably not that many people have ...

**2**

votes

**2**answers

195 views

### Integers up to n having an even number of trailing zeros in their factorial

It is well-known that the number of trailing zeros in the factorial $k!$ is given by the nice function $$ z(k) := \sum_{i \ge 1} \left\lfloor \frac{k}{5^i} \right\rfloor. $$
Now assume that we want ...

**0**

votes

**0**answers

74 views

### Minimize the length of two disjoint segments in the string with given property

You are given a string s of size n, consisting of characters A and B only. You have to find minimum sum of size of the two disjoint segments of the string s such that number of A's in them are >= z.
...

**3**

votes

**0**answers

138 views

### What is the function like when its Mobius inversion is $\sum_{w|r, (w,t)=1}\mu(w)q^{r/w}$?

Everyone, I am now reading a paper named The Irreducible Factors of $(cx+d)x^{q^m}-(ax+b)$ over $GF(q)$, http://qjmath.oxfordjournals.org/content/14/1/61.extract. And I’m confused with one of its ...

**0**

votes

**0**answers

64 views

### approximate coordinates in a one dimensional lattice

suppose I have a finite set of real numbers ${r_1, \ldots r_n \in \mathbf{R} }$ and a single real number $x \in \mathbf{R}$. Is there a fast algorithm for finding integer numbers ${i_1, \ldots i_n \in ...

**2**

votes

**1**answer

475 views

### Efficient algorithms to determine the roots of: $p(x) = r^x $ in the finite field $GF(q)$, where $r$ a primitive root of the field

I need to make sure that no efficient (i.e., polynomial time) algorithm exists for the following problem:
Exponentiating Polynomial Root Problem (EPRP)
Let $p(x)$ be a polynomial with $\deg(p) \geq ...

**8**

votes

**1**answer

507 views

### How to check whether a positive integer can be written as linear combination of given others, where all coefficients are positive?

Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient
algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that
$n = \sum_{i=1}^k a_i m_i$?
...

**6**

votes

**4**answers

489 views

### How long does it take to compute a class number?

I was wondering if there are any known (upper and lower) bounds for the complexity of computing the class-number of a finite extension of the rationals. (A general bound should be in function of the ...

**20**

votes

**4**answers

1k views

### Securing privacy of “who communicates with whom” under Orwell-like conditions

Assume that there is a big and powerful country with an
information-greedy secret service which has backdoors to all internet nodes
throughout the world which permit him to observe all exchanged data ...

**3**

votes

**2**answers

208 views

### Complexity of a problem remotely related to the discrete logarithm $A=x g^x$

Let $x,g \in \mathbb{F}_p^\ast$.
Given $g$ and either
$$ A = x g^ x$$
or
$$ A = x g^{x^2-1}$$
find $x$.
What is the complexity of solving this?
Is there a reduction to the discrete ...

**2**

votes

**1**answer

255 views

### (efficient) method to test $\{n\alpha\}\not\in [A, B]\subset [0,1]$

Suppose $\alpha$ is a fixed given irrational number with $\alpha\in [A, B]\subset [0,1]$, are there any (efficient) methods to compute the least integer $n$ such that the decimal part of $n\alpha$ ...

**9**

votes

**7**answers

2k views

### Is there an algorithm to solve quadratic Diophantine equations?

I was asked two questions related to Diophantine equations.
Can one find all integer triplets $(x,y,z)$ satisfying $x^2 + x = y^2 + y + z^2 + z$? I mean some kind of parametrization which gives all ...

**2**

votes

**1**answer

182 views

### RefReq: Algorithms for standard operations in Algebraic Number theory

Given an algebraic number field $F$ (I actually don't have an idea how to implement this data already, except for splitting fields of polynomials, but there is something in SAGE) is there free code ...

**28**

votes

**3**answers

2k views

### Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?

Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$,
decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective,
respectively, injective? --
And ...

**1**

vote

**1**answer

134 views

### What algorithms do you know for beltway reconstruction?

I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem?
Beltway Reconstruction Problem:
Assume there is a set of ...

**3**

votes

**1**answer

208 views

### Is the prime ideal principal which is in 256-th cyclotomic ring lying over 257?

As we known, the integer ring R of 256-th cyclotomic field is not a Principal Ideal Domain.
And rational prime 257 is split completely in R.
Suppose prime ideal P of R is an arbitrary ideal lying ...

**3**

votes

**1**answer

338 views

### Fastest Digit Extraction for Any Irrational Number

I believe the current lowest-memory algorithm for computing the $n^{th}$ binary digit of $\pi$ requires $O(log(n))$ bytes and $O(n^2 log(n))$ days (I pick Bellard over Bailey–Borwein–Plouffe for ...

**6**

votes

**2**answers

727 views

### Approximate number of primes below a given integer?

The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of witnesses to a TC0 ...

**2**

votes

**1**answer

321 views

### At what point does Miller-Rabin become faster than trial division?

I've read in various places (and know) that Miller-Rabin is a much faster primality test than trial division for large $N$, but is much slower than trial division for small $N$.
My question is: how ...

**9**

votes

**2**answers

594 views

### When polynomial f(x^2) can be factored as g(x)·g(-x) ?

In relation to my question Expression for the sum of square roots of zeros of a polynomial
How to characterize polynomials $f(x)$ with rational coefficients such that $f(x^2)=g(x)\cdot g(-x)$ where ...

**0**

votes

**0**answers

118 views

### Find polynomial in finite field

We have $A$, $B \in GF(q^k)$
We want to find polynomial $h \in GF(q)[x]$ where
$h(A) = B$
What is the lowest degree of $h$?
How to find $h$ with the lowest degree and what is complexity of this ...

**1**

vote

**1**answer

284 views

### Find root in finite field

What efficient algorithms exist for the solving $x^N = a$ in GF(q)?
What are their complexities?

**1**

vote

**1**answer

271 views

### calculate function from its divizor

There is elliptic curve $C (y^2 = x^3 + Ax + B)$ over $GF(q)$.
There is algebraic function f on C.
We have div(f).
How calculate f as rational function ( $f = (f_1(x) + yf_2(x)) / (g_1(x) + ...

**2**

votes

**0**answers

189 views

### Choosing a base where a given digit of a given number appears the most times

Is there an algorithm for choosing a base where a given digit of a given number appears the most times, that works better then trial and error? (see also this)

**1**

vote

**1**answer

253 views

### Computing the ratio of two large integers modulo m

$P(n)$ and $D(n)$ are two large integers.
Suppose $R(n) = \frac{P(n)}{D(n)}$ is an integer.
I want to compute $R(n)\bmod m$.
$P(n)$ and $D(n)$ are too large to be computed but $P(n)\bmod m$ and ...

**1**

vote

**5**answers

1k views

### The Inverse of the Euler Totient Function

How can we calculate the cardinality of the inverse of Totient function of any positive integer n ?
I tried going through this paper, but I couldn't understand the procedure.
Thanks

**2**

votes

**3**answers

2k views

### Algorithm for detecting prime powers

While reading Peter Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, I came across the following quote:
"This scheme will thus work as ...

**2**

votes

**3**answers

275 views

### Generating a set of integer passwords that can be securely authenticated

First, apologies for the title. This is an odd question, and I couldn't come up with a simple title for it.
My question is as follows.
Given a positive integer $k$, determine a set of properties ...

**1**

vote

**2**answers

771 views

### The relationship between the Dirichlet Hyperbola Method, the prime counting function, and Mertens function

I have a question concerning the connection between the Dirichlet Hyperbola Method and properties of both the Mertens function and the prime counting function.
Preliminary: Mertens function and the ...

**9**

votes

**3**answers

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

**3**

votes

**2**answers

669 views

### Find the maximum set whose subset sum is unique for every of its subset.

We are given a set of $n$ positive integers.
We assume all of them are bounded by a polynomial of $n$.
We would like to find a subset $S$ of numbers such that
for any $T_1,T_2\subseteq S$, the sum of ...

**6**

votes

**1**answer

598 views

### How this set of functions is ordered?

Notation:
$k, m, n$ are non-negative integers
$f, g, h$ are functions $\mathbb{N} \to \mathbb{N}$
$f^k$ is $k$-th iterate of the function $f$: $f^0(n)=n, f^{k+1}(n)=f^k(f(n))$
$f \prec g$ means ...

**16**

votes

**5**answers

3k views

### Fastest Algorithm to Compute the Sum of Primes?

Can anyone help me with references to the current fastest algorithms for counting the exact sum of primes less than some number n? I'm specifically curious about the best case running times, of ...

**5**

votes

**2**answers

310 views

### Feasibility of linear equations with few variables mod k

Say I want to verify the feasibility of
$$Ax \equiv b \text{ (mod } k)$$
where $A \in \mathbb{Z}^{m \times n}, b \in \mathbb{Z}^{m}$ and $k \in \mathbb{N}$. Is there a fast way to verify if there ...

**2**

votes

**0**answers

288 views

### Algorithm for keeping a concrete version of Euclid's argument simple

(A version of this same question was posted to stackexchange.)
Suppose we do what Euclid wrote about: starting with a finite set of primes, multiply them, add or subtract 1, factor the result, append ...

**3**

votes

**1**answer

395 views

### Find the least prime $p$ such that $mn$ divides $p-1$

My hope is that this question is "trivial," but it is outside my knowledge base, so I'd appreciate some advice.
Given positive integers $m$ and $n$, find the least prime $p$ such that $p-1 = mnk$ ...

**1**

vote

**0**answers

147 views

### Finding a set of congruences from a set of solutions

Let $S_1, \ldots, S_m \in \mathbb{Z}_2^n$ be $n$-tuples forming a subgroup of $\mathbb{Z}_2^n$. How can I find a set of congruences (mod 2) over $x_1, \ldots, x_n$ satisfying exactly $x_1 = S_j[1], ...

**0**

votes

**0**answers

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

**7**

votes

**2**answers

602 views

### Factoring some integer in the given interval

I'm posting this question here (rather than on CSTheory) since it seems to require much more knowledge about number theory than algorithms.
Let N be a positive integer. Is there an efficient (i.e. ...

**8**

votes

**1**answer

659 views

### The Number of Short Vectors in a Lattice

Given a lattice $L = \bigoplus_{i=1}^{m} \mathbb{Z}v_i$ (the $v_i$ are linearly independent vectors in $\mathbb{R}^n$) and a number $c > 0$, can one quickly compute or find a good estimate on the ...

**3**

votes

**0**answers

209 views

### Implementation for computing Shintani domains

By "Shintani domain", I mean a fundamental domain for the action of the totally positive units of a totally real number field k with $[k \colon \mathbb{Q}]=n$ (or more generally, those congruent to 1 ...

**11**

votes

**3**answers

767 views

### Bounds on squarefree numbers

Let $q_1,q_2,\ldots$ denote the squarefree integers 1, 2, 3, 5, .... What effective bounds are known for $q_n$? Clearly
$$q_n\sim\zeta(2)n$$
but I need hard inequalities. Of course from the above ...

**13**

votes

**2**answers

896 views

### Subfields of a function field

Is there an algorithm for generating (some or all) subfields of a certain genus of a given function field (even a random one,I mean for example generating a random elliptic subfield of a certain given ...

**4**

votes

**1**answer

344 views

### Can we count primes in residue classes quickly?

Using combinatorial methods (due to Legendre, Lehmer, Meissel, Lagarias, Miller, Odlyzko, Deléglise, Rivat, and probably others) it's possible to count the number of primes up to $N$ quickly -- in ...

**2**

votes

**5**answers

1k views

### partitioning a number into two sets based on sum of digits

hi, how can one determine whether a number belongs to such a set of numbers whose every element can be divided into two sets such that the sum of digits of each set of the number is same.
E.g
23450 ...

**6**

votes

**3**answers

920 views

### Prime counting - any fast alternatives to the Lagarias-Miller-Odlyzko combinatorial method or the Lagarias-Odlyzko analytical methods?

I guess the question says it all - I'm trying to track down fast algorithms for prime counting to know what's out there.
I'm already familiar with the two algorithms mentioned in the title ...