p0-Pollard implementation
A few things strike me as fairly obvious possibilities to consider here.

Use functions where appropriate


if(a&lt;0) a=-a;



I think I'd prefer to have a separate little function to compute the absolute value.

Be consistent


    while((a%2 == 0)&amp;&amp;(b%2 == 0)){
//        printf("step2\n");
        a=a&gt;&gt;1;
        b=b&gt;&gt;1;
        c*=2;
    }



I'd pick either bit-oriented or mathematically-oriented operations, and use them consistently. That would mean either using shifts and bit-tests throughout:

 while(((a &amp; 1) == 0) &amp;&amp; ((b &amp; 1) == 0)){
        a &gt;&gt;= 1;
        b &gt;&gt;= 1;
        c &lt;&lt;= 1;
    }


...or else using mathematical operators throughout:

 while((a % 2 == 0) &amp;&amp; (b % 2 == 0)){
        a /= 2;
        b /= 2;
        c *= 2;
    }


Also note the compound assignment operators--at least in my opinion, they're much clearer than things like A = A &gt;&gt; 1. Maybe it's just a background in math, but I've never like things like A = A + 1; that always look to me like they're just clearly false statements.

Better variable names

Most of your variable names are so short they're basically meaningless--a, b, d, x1, x2, and so on. I'd much rather see names that made their intended use/purpose easier to understand. 

Type checking

Although it can quickly get into extremely advanced programming, I'd at least consider adding some type-checking to your templates. Just for example, I'd guess all the templates in this code really only make sense if T is some integer type, not floating point, a string, etc. That being the case, it's fairly easy to add at least minimal type-checking to enforce that. One simple form of that would use static_assert:

template &lt;typename T&gt;
T gcd(T a, T b){
    static_assert(std::is_integral&lt;T&gt;::value, "Only integer types allowed");


The code almost certainly won't compile if somebody attempts (for example) to get the GCD of two strings--but with the static_assert, you're pretty much guaranteed that at least part of the error message they get will say "Only integer types allowed". Without it, they're likely to get a giant avalanche of error message telling them about things like there not being an &gt;&gt; overloaded for string and int, followed by a 5-page list of the overloads of &gt;&gt; that it considered and rejected in trying to figure out a way to compile the code.

Note: there's work in progress on a set of extensions to C++ called "Concepts" to support this a little more directly in the language. Some compilers already have experimental support, in case you want to try it.