基于身份的密码体制可弥补传统的基于证书密码体制的不足，因此近年来发展迅速。基于身份密码体制的基本工具是双线性对，其有效实现取决于双线性对的计算效率。但就目前而言，双线性对的计算效率相对于实际应用中的要求仍存在差距。本文的主要研究内容之一，正是对降低双线性对的计算开销、提高算法实现效率的讨论。所获得的一些独立工作成果如下：　　 1.双线性对的计算效率与Miller循环运算量密切相关。基于整数的稀疏表示及预处理的方法，本文提出了一类降低Miller循环运算量的改进方案，包括基于NAF、固定基、滑动窗口等的加速算法，并对预处理方法做了一些更深入的讨论。在一定条件下，对宽度为4的滑动窗口NAF加速算法，其Miller循环的平均运算量比一般Miller算法减少约1/6。　　 2.给出了一个自下而上的完整的双线性对算法实现方案，进行了详尽的时间复杂度分析，并且提出了一些具体的改进思路。本文还据此编写了一套完整的双线性对计算程序，大量的数值计算测试表明该程序具有准确性和高效性。　　 3.双线性对计算的复杂性，也表现在参数选择的困难性，包括参数点选取的困难性。本文针对这一困难性作出了具体的分析，并提出了若干解决思路。　　 4.对于双线性对核心算法的若干关键问题，提出加速改进方法。其中包括：(1)优化Tate对计算的Miller算法，合并了直线函数的计算(gU/V、gU+V)与椭圆曲线点的累加(U+V)操作中的重复计算部分，使得这三步计算减少了一半的运算量；(2)对利用Weil定理递推计算扩域上椭圆曲线阶的算法，提出了一个基于反复平方-乘思想的改进，将算法的复杂度由O(kL2)降为O(L2log2k)；(3)针对求有限域上平方根的算法，提出了一个适于程序实现的改进方案，将其算法复杂度降为O(L3)。　　 本文最后给出了一个双线性对的应用实例。在Libert-Quisquater签密方案的基础之上，本文借助马步遍历置换算法，构造了一个基于Ate对计算且适用于长消息的签密方案。