# Tagged Questions

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

**6**

votes

**3**answers

637 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?

**8**

votes

**0**answers

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

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

**5**

votes

**2**answers

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

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

**1**

vote

**1**answer

280 views

### Computation for composition of polynomials

Let $R$ be a ring, $f(X)$ be a polynomial with coefficients in $R$ of degree $n$. It's known that for any $\alpha \in R$, one can evaluate $f$ at $\alpha$, i.e compute $f( \alpha) $ in $O(n)$ ...

**7**

votes

**1**answer

641 views

### Best way to find a closest vector in a lattice

Let $v_1,\ldots,v_n$ be linearly independent vector in $\mathbb{R}^n$, and let $\Lambda=\oplus_i^n \mathbb{Z}v_i$. The question is, given a vector $w$ find the element $v$ of the lattice $\Lambda$ ...

**13**

votes

**2**answers

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

**5**

votes

**2**answers

526 views

### Next (Restricted) B-Smooth Number Problem?

Given a bound, $B$, and a list of (small) primes $(p_0, p_1, \dots, p_{n-1})$ is there an efficient algorithm to find the next number greater than $B$ that can be expressed as a product of primes from ...

**5**

votes

**1**answer

262 views

### Speeding the quadratic sieve with an oracle

Suppose we have an odd composite $N$ and want to find numbers $a_1,\ldots,a_k$ such that each $a_i^2$, reduced mod $N$, is $b$-smooth. Of course we can use the quadratic sieve algorithm (minus the ...

**0**

votes

**3**answers

327 views

### Differences of squares

Suppose I wanted to express a number $N$ as a difference of squares. For large $N$ this is in general difficult, as finding $N=a^2-b^2$ leads to the factorization $N=(a+b)(a-b)$. Even if the problem ...