它比这个快吗?

从您已经编写的内容来看,似乎只能进行微不足道的优化。

// Get rid of the inline, it's pointless for functions this large.
// Some compilers might remove the inline for big functions.
int legendre(int pa, int pm){

// Rather than creating variables here, you COULD make global
// variables and assign them here. That would get rid of some
// time taken creating these local variables.
register unsigned int a = pa;
register unsigned int m = pm;
int t = 1;
int tmp=0;
while (a>1) {
    tmp=__builtin_ctz(a);//a=x*2^tmp, where x is odd
    a>>=tmp;

    // This just throws both if-statements into one.
    if((tmp&1 &&((m&7)==3 || (m&7)==5))
       || ((a&3)==3 && (m&3)==3)) t = -t;
    m %= a;
    tmp=a;
    a=m;
    m=tmp;//exchange variables
}
if (m == 1) return t;
return 0; 
}

除此之外,这个代码看起来不错。我认为你不必担心。

我能看到的唯一可以优化的是符号翻转:

t = (t ^ -1) + 1

或

t = ~t + 1; // I don't prefer this one

有趣的是,在某些平台上,尤其是虚拟机上,速度可能会慢一些,所以你必须手动检查。

编辑 :

好吧,发现了一件我忽略的好事,你创建了一个临时变量来交换它们,你可以使用XOR,因为它们都是整数:

m = m^a;
a = a^m;
m = m^a;

这样,变量就可以交换它们的值,而不需要temp-var