All Questions
Tagged with factorization reference-request
25 questions
1
vote
1
answer
178
views
+50
On a probabilistic integer factorization algorithm given bounds for one prime factor
We got a probabilistic integer factorization algorithm and experimental evidence with large
integers given bounds for one factor.
Let $D \ge 2$ be real number and let $p,q$ be primes and $N=pq$.
...
- 25.4k
9
votes
0
answers
275
views
What is known about vector subspaces of polynomial rings closed under factors?
Let $R$ be a commutative ring. Call a nonempty subset $F$ of $R$ a factroid if it is closed under sums and factors. That is:
If $a,b \in F$, then $a+b \in F$, and
If $a,b \in R$ with $a\in R$ ...
- 1,802
4
votes
0
answers
119
views
Adjoining new factors for primes in UFDs
It is well-known that if we pass from a UFD to a new ring where we have factored one of the primes, it does not need to stay a UFD. The classic example is passing from $\mathbb{Z}$ to $\mathbb{Z}[\...
- 18.7k
0
votes
0
answers
65
views
Reference Request: Factorization method for polynomials whose maximum absolute value of coefficient is 1
So, today I came up with a method for factoring polynomials whose coefficients are either $-1$ or $1.$
Let me explain with examples.
Example No. 1. Factorize $P(x)=x^8+x^7+1$
Solution. It is known ...
- 161
3
votes
3
answers
382
views
Closed formula for number of ones in a proper factor tree
Edit [2023 Dec 7]: One of my specific wonders, along with that of students, is around when a recursive formula might have – or be expected to have – an explicit or closed formula. What is the ...
- 7,831
5
votes
0
answers
66
views
weak factorization systems (co)generated by an arbitrary class of morphisms
Under what assumptions can one prove existence of weak factorization systems (co)generated by a class of morphisms ?
Are there counterexamples ? I am interested both in assumptions on the class of ...
- 513
4
votes
0
answers
216
views
Characterizing atomicity in a commutative domain
In Proposition 1.1 of [Math. Proc. Cambridge Phil. Soc. 64 (1968), No. 2, 251-264], P.M. Cohn famously claimed (without proof) that a commutative domain is atomic if and only if it satisfies the ...
- 10.5k
2
votes
0
answers
140
views
Integers with exactly three factor pairs whose successors are relatively prime
I am interested in the following problem, and will appreciate pointers around how it can be solved – partially or fully – and/or indicators around whether it is even tractable:
Characterize $N \in \...
- 7,831
0
votes
0
answers
138
views
A diophantine equation involving partial sums of exponentials similar than the equation in Fermat's Last Theorem
I'm curious about the following diophantine equation from my invention: I don't know if this is in the literature, I wrote it using creativity in an attempt to write a variant of the equation in ...
6
votes
2
answers
804
views
Must Mersenne numbers be divisible by arbitrary large primes with exponent one?
Let $M_n$ denote the Mersenne numbers $M_n=2^n-1$.
As $n$ varies, must $M_n$ be divisible by arbitrary large prime $p$
with exponent one, i.e. $p \mid M_n, p^2 \nmid M_n$?
In other words, must the ...
- 25.4k
3
votes
1
answer
137
views
Subexponential algorithms that apply only one of factoring and discrete logarithm?
Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants.
What are the subexponential ...
- 13.9k
4
votes
1
answer
138
views
Irreducible skew polynomials over an algebraically closed field
Let $\mathbb{F}$ be a field, and denote with $\mathbb{F}[t,\sigma]$ the skew-polynomial ring, where $\sigma$ is an automorphim of $\mathbb{F}$. Recall that the multiplication of this ring is defined ...
4
votes
1
answer
288
views
Is total degree version and $x,y$ degree version of Coppersmith's theorem correct?
The notes here https://web.eecs.umich.edu/~cpeikert/lic13/lec04.pdf have the note 'Small decryption exponent $d$: so far the best known attack recovers $d$ if it is less than $N^{.292}$. This uses a ...
- 13.9k
4
votes
1
answer
414
views
A Handbook of Matrix Factorizations
I am looking for a good collection of facts regarding the various types of matrix factorizations, something like a "Handbook of Matrix Factorizations" or a very-thorough review paper. I am hoping for ...
- 143
7
votes
1
answer
382
views
$\log \log p / \log \log n$, where $p|n$, gets equidistributed in [0,1] (for almost all $n$)
According to Hardy-Ramanujan/Erdős-Kac we know that usually there are $\sim\log\log n$ prime numbers in a factorization. But if you pick up a natural number at random, and you factor it, what is the ...
- 1,384
4
votes
2
answers
199
views
Counting integers with k large prime divisors
If $x \ge y \ge 1$ are real numbers and if $k$ is a positive integer, take $\Phi_k(x, y)$ to be the number of integers $\le x$ with exactly $k$ prime factors and no prime factor $\le y$. If $y$ is ...
- 443
12
votes
2
answers
4k
views
How can one construct a sparse null space basis using recursive LU decomposition?
Given an $m$ by $n$ matrix $A$ I'm familiar with the standard method to compute a basis for the null space of $A$ by computing a QR factorization of $A^T$. If $A$ is large and sparse, we can use ...
- 723
2
votes
1
answer
450
views
Is there a "small $\omega$" number theorem?
In my studies of how primes jump (search this forum for a link), a question has been raised which may have been studied. Can anyone jump-start my literature search with references regarding the ...
- 13k
3
votes
1
answer
313
views
Irreducibility of family of polynomials
Consider the following family of polynomials over $\mathbb{Q}$:
$$f_n = x^n - x^{n-1} - \dots - 1$$
Notice that these polynomials satisfy the recurrence
$$ f_{n+1} = x f_n - 1 $$
I would like to ...
- 173
5
votes
1
answer
214
views
Dynamics of the distribution of prime factorization types in increasing intervals
I've tagged this as reference request as surely this question must be very well investigated, I just don't know how to look for it. Most likely the perfect answer will be in form of a keyword for ...
- 18.4k
9
votes
2
answers
1k
views
runs of consecutive non squarefree integers
This question gained no attention at Math SE.
Call a sequence of $k$ consecutive naturals squary if each one of them is divided by a square > 1. The Chinese Remainder theorem trivially guarantees us ...
- 13.4k
6
votes
1
answer
1k
views
Using the decomposition $641 = 5^4 + 2^4$ to factor $F_5$
The question in the title arises from a problem in Stewart's "Galois Theory, Third Edition" (and possibly elsewhere) which has been bugging me for a few days since reading it:
Problem 19.5 (p. 224) ...
- 5,191
9
votes
3
answers
980
views
$\omega(p^n - 1)$ as $n \rightarrow \infty$
Although I am also interested in the number of distinct prime factors (not counting
multiplicity), today I use $\omega(m)$ to denote the number of (positive) prime
factors (with multiplicity) of the ...
- 2,158
12
votes
5
answers
2k
views
Polynomials all of whose roots are rational
I have two questions about the class of integer-coefficient polynomials all of whose roots are rational.
I asked this at MSE, but it attracted little interest (perhaps because it is not interesting!)
...
- 151k
5
votes
0
answers
682
views
Is integer factorization harder than RSA ($n=pq$) factorization? [closed]
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 $...
- 236