# Tagged Questions

The tag has no usage guidance.

451 views

### Given an arbitrary composite odd integer $N$, find two integers $P$ and $Q$ such that $P-Q \neq 1$ and $N=P^2-Q^2$ [closed]

Given an arbitrary composite odd integer $N$, find two integers $P$ and $Q$ such that: $P-Q \neq 1$ and $N=P^2-Q^2$ I am assuming that the best known solution to this problem runs at $O(2^{|N|})$. ...
141 views

211 views

352 views

262 views

491 views

### Are these polynomials irreducible over ring Z of integers ?

Is it true that polynomials of the form : $f(x)= x^n+x^{n-1}+...+x^{k+1}+ax^k+ax^{k-1}+...a$ where $gcd(n+1,k+1)=1$ and $a\in \mathbb{Z^{+}}$ are irreducible over ring $\mathbb{Z}$ of ...
420 views

### Finding a divisor of a number under a constraint

Given 2 positive integers $n, l$ with $l \leq n$, I am looking for a way to find the largest divisor $d$ of $n$, such as $d \leq l$. Assume $n$ has too many divisors for an exhaustive search. Thanks ...
3k views

### Evidence for integer factorization is in $P$

Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...
2k views

### Finding the greatest (smallest) factor of a number smaller (greater) than another number

Instead of iterating through all the possible numbers, is there a better way to find the greatest factor of a number $n$, such that it is less than $m$ ($m$ < $n$). Similarly how does one find the ...
486 views

### Factoring and Index Calculus and duality between DL and factoring via compuational problems made easy through them

If factoring is in $P$ (with a blazing fast polynomial time in $P$), would it affect the index calculus algorithm used for Discrete Log calculation in any serious way? Other connections $1.)$ "...
553 views

### Is this pleasing polynomial irreducible?

Let: $f(x)=x^n+2x^{n-1}+3x^{n-2}+4x^{n-3}+\ldots + (n-1)x^2+nx+(n+1)$. Is $f(x)$ irreducible? In light of the answers to this question, I now know that this is true when $n+1$ is prime. What about ...
636 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. ...
257 views

### 10 factors for x^2 coefficient in quadratic sieve?

I wrote a quadratic sieve and I tried plugging in all the same parameters as the wikipedia article says msieve uses: http://en.wikipedia.org/wiki/Quadratic_sieve#Parameters_from_realistic_example It ...
2k views

### Reduction from factoring to solving Pell equation

The paper Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem claims There are reductions from factoring to solving Pell’s equation, and from solving Pell’s ...
601 views

### Least Prime Factor in a sequence of 2n consecutive integers

I was thinking about consecutive integers and I wondered if anyone had done work exploring whether a sequence of $2n$ consecutive integers (i.e. 101,102,103,...,100+2n) always contains at least one ...
1k views

### Factoring Integers using Complex Integrals

Suppose $n$ is an integer and we wish to factor it. As a special case we have $n = pq$ with $p,q$ distinct primes. The problem: factoring $n$ via complex analysis tools Background I have been ...
This is a repost. I could not get a precise answer on math.SE and cstheory.SE Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers $... 1answer 647 views ### What are the chances of finding a small factor? EDIT 2011.05.09 Thanks to Junkie and Tapio Rajala for checking on me. While most of the candidates referred to below have small factors, the "large" small factors I list below are incorrect. Also, ... 2answers 608 views ### when does a regular graph have a 1-factorization? Is there a sufficient condition for a regular graph to have a 1-factorization (i.e. being able to pack all of its edges into disjoint perfect matchings, and excluding one vertex if the number of ... 1answer 133 views ### “locally” factoring subgroups of Lie groups I'm not really a math person, and apologize if the question here is too simple. I've ended up with the following type of question for a few Lie groups, but state it for SO(n). I start with a subgroup ... 3answers 2k views ### Density of Irreducible Polynomials in$\mathbb{Z}[x]$Recently I was thinking about some questions concerning$\mathbb{Z}[x]$and realized that they might be a bit easier if I knew the relative densities of reducible polynomials. Let$P_d$denote the ... 2answers 562 views ### Second stage of elliptic curve factorization via random walk/Pollard's rho in constant (or low) memory? The second stage of elliptic curve factorization has the drawback of large memory usage. Let$n=pq$,$E(\mathbb{Z}/n\mathbb{Z})$is elliptic curve and$P$point on$E(\mathbb{Z}/n\mathbb{Z})$. On$...
I'm interested in factoring a finite set of $n$-tuples as the Cartesian product of two "factor sets", of which the first factor is itself the Cartesian product of some of the set's projection images, ...