-1
$\begingroup$

My question was closed on Theoretical computer since.

May I publish the modified version of it here?


I am working on Integer Factorization problem, and I came to idea of applying Fermat's sieving improvement in multiplication.

Let it be $N$ the value we want to factor, such that $$N = ab$$

Now I want to take a small prime value $k$ and find all the possible values of $a$ such that: $$(a\mod k)(b\mod k)=N\mod k$$

This will allow me to find the factors of $N$ by using the next algorithm

    set 'options' as a group of all the values of a as described above

    while i smaller than N do
        while j smaller than options length do
            test if i*k + options[j] is a factor, in case it is, finish and print it
            set j to j + 1
        end while loop
        set i to i + k        
    end while loop

But it doesn't stops here, next I want to take the next prime value after $k$, let it be $l$, find it's group of optional values of 'a', and merge it with the 'k' group, using the next algorithm

 return all the shared values of j and l groups over jl cycle

The problem is that I don't know if applying the factory algorithm on 'l' group will find the factor $a$ or $b$, so I can't know for sure if the merged group will find the factor $a$

Question

For the next input

  • $N$ - big integer with only two non trivial factors.
  • $k, l$ - two small primes

I want to get the next output

  • a group of integers between 0 - $kl$ that has less than $kl$ values and can be used in my factory algorithm to find the factors of $N$, the group should be created using the merge as described above.
$\endgroup$
8
$\begingroup$

Yes, you could. However, I don't know that it's going to be very well received unless you also make some significant improvements to your explanation of the question. Right now the question is hard to understand and rather incoherent.

The fact that it's closed on CSTheory doesn't automatically make it ineligible here. CSTheory is focused on research-level questions, whereas we don't have that requirement here, so a question that was closed because it wasn't research-level could potentially be a good fit here.

That said, your question has many other issues that I strongly encourage you to fix before you post here.

  1. Java code is inappropriate here. Use pseudocode, and make sure it is concise. People are unlikely to read a wall of text or a wall of pseudocode.

  2. Make sure your question is very clear, and define all terms before using them. Right now it's hard to extract what your question is. It seems your question is an algorithm design question, but you have not clearly specified what problem you want an algorithm for. You say "How can I make the merge?", but you haven't defined what you mean by "the merge".

    A good tip for specifying algorithm design problems is to describe the input, the desired output, and give a mathematical specification of what correct output is. If you have other requirements, give them as well.

    Also, it's not at all clear what "without been worry to get both a and b sieved out" means. Please, take the time to proof-read through your question and state it as concisely and clearly as possible.

    Finally, I find it extract what's going on with the first few paragraphs of your question. You are just throwing around equations but it's not clear to me where the quantities come from or what you are trying to achieve or what those equations have to do with your goals.

  3. Finally, the other challenge is that you are trying to ask about solving a known-hard problem that has been studied extensively, a problem that requires considerable mathematical background to make progress on and where progress requires a deep understanding of past work and known barriers to progress, yet the question does not show any evidence of having reached that level of understanding. This makes it less likely that the question will be valuable or useful to others.

    The premise of your question is that a solution to your specific algorithm design problem is going to give you a fast factoring algorithm (something tons of researchers have tried and failed to achieve). However, given this history, it's not likely that you're going to be able to find a fast factoring algorithm, especially given that your question doesn't appear to demonstrate knowledge of the background needed to understand the existing literature on this area, and given that the question does not seem to demonstrate awareness of even the most basic barriers to a solution (such as the need to avoid enumerating through exponentially many candidate factors). Therefore, questions of the form "help me debug my hopeless broken algorithm to this known open problem" are going to be very challenging to turn into a good question, and are going to require extraordinary effort on your part to articulate a good, well-researched question that will be helpful to others.

    See How to deal with questions about crank-heavy topics? and How to ask P vs NP questions without getting closed? for questions that might have some helpful advice (even if they're not exactly the same situation). Also, over on CS Theory, see the following, which also have helpful advice: https://cstheory.meta.stackexchange.com/q/2720/5038 and https://cstheory.meta.stackexchange.com/q/1058/5038 and https://cstheory.meta.stackexchange.com/q/1026/5038 and their policy on unpublished not-peer-reviewed approaches to open problems and crank-friendly topics (their policy is not necessarily binding on CS.SE, but it will be helpful for you to understand what is behind those policies and the advice there on how to make your question better).

In short: If you just re-post the same question here as you posted there, I predict that the question is not likely to receive a good answer, for the reasons articulated above.

$\endgroup$
  • $\begingroup$ I just edit it, do you think it's a reasonable question now? $\endgroup$ – Ilya Gazman Feb 26 '15 at 0:06
  • 2
    $\begingroup$ @Ilya_Gazman, based on the revision, it looks like the fundamental problem is that your approach to factoring is a dead end. There's no way this is going to lead to a good algorithm for factoring because the number of such values of $a,b$ is exponentially large, so you're going to get a factoring algorithm that is far slower than the state of the art -- so the question is overly specific and overly focused on an approach that doesn't seem like it'll work. Therefore, if I'm understanding your approach correctly, it won't be easy to extract a good question from this. $\endgroup$ – D.W. Feb 26 '15 at 1:01
  • 1
    $\begingroup$ The best I can suggest is to back up a step and ask about the basic approach: If I can enumerate all $a$ such that $(a \bmod k) \times (b \bmod k) = (N \bmod k)$, will that help me factor $N$? In other words, ask about the implicit premise behind your question, rather than asking the complex question itself. But really, this might not be the site for trying to ask others to help you debug your approach to solving famous open problems. I've edited my answer; see point 3 above. You'd do better to ask about the barriers to finding a fast factoring algorithm (after doing extensive research). $\endgroup$ – D.W. Feb 26 '15 at 1:19
  • $\begingroup$ Wow, thanks for your brief answer! I spent the last months studding this subject, I think that I understand the Quadratic sieve, and the general approach, and I am getting the feeling about how many people are trying and failing to improve it, so I do not dream of beating them. But I do like the subject and there for I choose a direction and I am trying to study it. May be I will fail too, but I like it, so I explore. Before posting this question I been using the same method on merging on squares. Will continue on the next comment $\endgroup$ – Ilya Gazman Feb 26 '15 at 4:15
  • $\begingroup$ Just like my link to wiki suggest. Take all the possible solutions of $$x^2\mod k-c\mod k=b^2\mod k$$ and use the algorithm from my question to factor. How ever in this case I do not have the problem as in my question, and merging does work. The number of the values in the group has exponential growth, but so is the ratio between the cycle size and the number of the values in the group. I been able to factor 90 bit values using this method. It's a very small value, if comparing to quadratic sieve, but... Will continue next comment. $\endgroup$ – Ilya Gazman Feb 26 '15 at 4:22
  • $\begingroup$ It made me curios and since I did not found many researches with this idea, I decided to explore. Sieving squares fails, because the number of the values in the group is growing with multiplies of 10 - 100 while the ration between the group size to the values, in multiplies of 2-2.5, I only been able to get a ratio of about 20,000. This is why I am trying it from different direction, I want to combine the two some how. Try to sieve $x−b$ and $x+b$, with multiplication I can also use the fact that $x-b$ is a prime. There are many directions there and there for I am exploring. $\endgroup$ – Ilya Gazman Feb 26 '15 at 4:29
0
$\begingroup$

If you get rid of Java and replace it with concise pseudo code, I don't why I not.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .