右值(rvalues)和右值引用(rvalue references)是支撑Modern C++的中流砥柱、构筑C++效率极限的基石之一。

右值、右值引用简介

值和变量类型基础知识

在开始探索这片“天柱城”前，需要先明确C++中值和变量的类型。
值和变量的类型和定义等不要混淆！
每个C++表达式（一个操作符(operator)和若干操作符(operands)、一个字面量、一个变量名等等）都可以视为一个值。
值依照其是否named/can be moved-from 只有 左值、将亡值、纯右值 类型(types)之分；
变量(variables) 只有各种类型(categories)之分；变量一定是具名的，值可能不具名。

1
2
3
4
5

int x = 3; //声明了一个变量x，使用数字常量值3初始化之，3是纯右值
int y = x; //声明了一个变量y，将变量x作值并初始化之，x是左值
x = std::move(y); //此时std::move(y)是将亡值
int fun(){return 1;} //1是纯右值，但fun()的返回值是将亡值（传统意义上的“右值”）
int& bar(int& ref,int add){ref += add;return ref;} //bar()的返回值是左值

变量(variables)可以分为fundamental types和compound types二大类。

• 第一种是内置/基本数据类型，简而言之其包括integral types、floating point types、void和std::nullptr_t(C++11)。
  其中integral types主要包括int、char及它们的unsigned、long(long long)、short版本（部分平台上还有uint_8一类的实现，但都属于“integral”之类，下同）、bool。
  floating point types主要包括float、double及它们的long版本。
  integral types 和 floating point types 又统称 arthimetic types（算术类型）。

• 第二种包括reference、pointer、pointer-to-member、array、function、enumeration和class。其中，reference不占有独立的内存空间。

C++98——前尘往事

C++中引用是一种特殊的变量，和多数语言一样，其相当于是一个其它变量的别名(alias)，指向的对象使用的是既有的内存空间。
C++允许对所有的 complete types （完备类型）对象建立引用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int x = 1;
int& r1 = x; //对基本变量的引用

int fun(){}
int (&r2)() = fun; //对函数的引用

int arr[5]={};
int (&r3)[] = arr; //对数组的引用

int* ptr = nullptr;
int*& r4 = ptr; //对指针的引用

struct T{int x;} a;
T& r5 = a; //对结构体/类的引用
int T::*&& r6 = &T::x; //对pointer-to-member的引用

enum class U{a,b};
U c{};
U& r7 = c; //对enum的引用

与Java、Python等语言中的“引用”稍显不同的是：

• C++的引用变量必须建立时就被初始化且绑定到一个对象上，不存在空引用(Null reference)。相比之下Java等允许初始化一个空的引用变量NullPointerException警告
  
• C++的引用变量一旦初始化，则不能再指向其它对象（作为一个compile-time language，好像你也没办法让它指向其它对象，毕竟operator=接下来都直接作用在对象本身身上了），相比之下Python等就支持引用乱窜

引用的可变性也是Python等语言中初学者常容易感到困惑的地方，尤其是python弱类型的特性导致难以判断到底是创建了一个新的对象，还是只是引用改指向另一个对象等等。

C++中，虽然没有null references，但其存在极大量的悬挂引用(dangaling references)，且悬挂引用的处理时至今日依然是C++ Languages的一个核心议题之一。

C++中引用和指针的小比较：

• C++中引用必须被初始化，而指针可以不被初始化野指针；引用必须指向一个对象，指针可以指向NULL(C++11请改用nullptr)；引用不能更改指向，指针不被底层const约束者可以更改指向。
  
• C++中引用不是对象（References are not objects），所以不存在“引用的数组”、“指向引用的指针”和“指向引用的引用”(There are no arrays of references, no pointeres to references and no references of references)；（注意指向引用的指针不要和指向指针的引用混淆，指向引用的引用不要和右值引用混淆，引用符号永远后置）

其实C++引用在编译阶段（底层）的实现原理依然是指针，引用宏观上可以视为一个被自动解引用的、被底层const约束的指针(形如int* const)，毕竟建立即必须初始化等特性与之同样相衬。

C/C++11前，表达式的变量类型被分为左值(lvalue)、非左值对象(non-lvalue object)和函数调用者(function designator)。非左值对象就是常说的“右值”(rvalues)。
其中左值都会具备 object identity （即其具备存储空间等等），右值相反。
基本上C/传统C++的表达式左右值都不难辨别，“考古”部分也不多赘述，毕竟真的要用的时候cppreference随时都可以翻。
同时，C语言中由于并没有函数/运算符重载的概念，因此modifiable lvalues 就是lvalues 的一个真子集，即能放在（复合）赋值运算符左侧的一定是左值。

C++11前的引用只有lref和const lref两种，后者亦被简称为“常引用”。其中，左值引用只能绑定至左值上，常引用可以被绑定至左值或右值上。
二者的不同在于能否通过这个引用去修改指向对象的值，相当于是否有顶层const对指针的约束。

C++11——风起云涌

右值引用之所以被冠以如此重要的地位，在于其远不仅是提供了增加了一个语法点/编程方式，而是彻底地改变了C++11以来程序设计的逻辑，尤其对template programming影响极为深远。

先来简单介绍下右值引用(rvalue reference)的概念：
创建一个右值引用的方式是在变量后缀加'&&'，形如int&&，注意两个&中间不能加空格（不然就成引用的引用了）
右值引用也是引用的一种，自身不占据内存空间，亦不是对象，遵循引用的相关规则（必须初始化等）。
区别是，在初始化时，右值引用只能被绑定至右值上；但不同于常引用，其绑定后可以通过它修改指向对象的值。

此处不讨论const rvalues(形如const int&&)，原因另起炉灶再讲；此外，相信你对移动语义理解足够深刻时，对const rvalues这一问题的理解也能水到渠成。

在右值引用配套建设上，C++11让static_cast新增从左值向右值转换的功能。如static_cast<int&&>(x);可以让一个int的左值x“变成”一个右值。
同时新增了一个函数std::move，其有一重载提供了编译期的更加直观的代码转换（“套皮”）：

1
2
3
4
5

template<class Ty>
constexpr std::remove_reference_t<Ty>&& std::move(Ty& arg) noexcept
{
    return static_cast<std::remove_reference_t<Ty>&&>(arg);
}

（哈，一不小心又挖到了C++11的两个新坑：constexpr和noexcept！等等，是不是还踩了万能引用和引用折叠的坑？不，你什么都没看到）
关于左值引用、常引用和右值引用的常见绑定规则：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int main()
{
    int x=1;
    
    //lvalues can be used to initialize l-ref and c-ref
    int& r1_1 = x; //OK
    const int& r1_2 =x; //OK
    //int&& r1_3 = x; //Not compile: invalid binding

    //rvalues can be used to initialize r-ref and c-ref
    //int& r2_1 = 1; //Not compile: invalid binding
    const int& r2_2 = 1; //OK
    int&& r2_3 = 1; //OK

    //std::move can be used to "move" a lvalue to a rvalue
    int&& r3_3 = std::move(x); //OK
    return 0;
}

C++17——惊鸿照影

C++17中对左右值进行了进一步细分、归类。具体来说，

• 每一个值一定是 {左值(lvalue)、将亡值(xvalue)、纯右值(prvalue)} 中的一种；
  
• lvalue和xvalue并称为“泛左值”(glvalue)，xvalue和prvalue并称为“右值”(rvalue)。

冰知识：lvalue的全称应为 locator value（而非"left-value"）。

辨别一个值属于哪个类型，cppreference上有一段非常简明扼要的分类原则：

Values that are named and can be moved-from are xvalues;

Values that are named and cannot be moved-from are lvalues;

Values that are unnamed and can be moved-from are prvalues;

Values that are unnamed and cannot be moved-from are not used.

预告：下面“悉数言之”信息量极大

左值

下述表达式是左值(lvalues)：

• 所有的具名变量本体、函数名、模板参数对象(template parameter object)和类内的数据成员；引用类型的变量无视其引用类型，均为左值（点名"rvalue references are lvalues"）；
  
• 返回左值引用的函数/重载运算符的返回值；
  
• 所有内置的赋值运算符和复合赋值、前置自增/减、解引用、取下标、取成员、解引用成员、取成员/解引用成员指针(.*、->*)运算符；
  
• 字符串字面量(string literal)；
  
• 向左值引用的类型转换（cast）；
• 左值引用作为模板参数(non-type template parameter of lvalue reference type)；
  
• 对函数的右值引用(???)；
  
• 特定条件下的内置逗号(,)、三元条件运算符(a ? b : c)（一般要求运算符右侧的一个/两个参数都是左值）；

下面代码中出现了大量左值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

int a = 0; //a是左值
int b() //b是左值
{
    a += 1; //表达式是左值
    ++a; //左值
    int c[5]{}; //左值
    c[3]; //左值
    a = 5; //左值（表达式整体）
    "Hello, World!" //左值
    int* ptr = &a;
    *ptr; //左值
    *ptr ? a : c[2]; //左值
}

struct T{int x;}
int main()
{
    T a;
    T* b = &a;
    a.x; //左值
    b->x; //左值
}

分类的作用自然是帮助我们更好地辨别其性质。左值的独有性质如下（充分必要条件）：

• 左值（未重载operator&()）可以被内置取地址运算符获得其地址。如&std::endl;、&++i;、&"Hello, World!"均为合法的表达式。
  
• 可更改的左值（含引用）可以被内置的（复合）赋值运算符赋值。
  
• 左值可用于初始化一个左值引用(lvalue reference)（const lvalue约束另计）。

划重点：

• 唯一一个“永远”正确的区分左右值的标志是能否被取其地址。
• 作为（复合）赋值运算符的左操作数 是 其为左值 的既不充分也不必要条件，因为常左值不能被赋值，且operator=可以提供面向右值的重载。

纯右值

纯右值(pure rvalue,简称prvalue)是一种更偏向“传统”观念上的右值。
下述表达式是纯右值：

• 除字符串字面量外的字面量（常量），含枚举类型；
  
• 返回非引用类型的函数/重载运算符的返回值；
  
• 内置的后缀自增/减、算术、逻辑、比较、取地址运算符；
• this指针；
  
• 向非引用类型的类型转换（cast）；
  
• lambda表达式；
  
• 概念(concepts)；
  
• 模板参数列表中的非类型的、scalar-type 的参数；

  1 2 3 4 5 6 7 8 9 10 11 12 13

  template<size_t v> int fun() { &v; //Not compile: cannot take address of prvalue "v"(template non-type scalar parameter) &1; //Not compile: cannot take address of prvalue 1(numeric constant/literal) v = 1; //ill-formed: lvalue required as left operand of builtin assignment operator } int main() { fun<1>() = 2; //Not compile }

C++17提出了复制省略(copy elision)（又名 prvalue sematics），要求编译器对纯右值进行复制省略优化，史称"URVO"(Unnamed Return Value Optimization)。

将亡值

将亡值(eXpiring value,简称xvalue)的概念在C++17中从“右值”的混沌中区分开来（不过二者仍有诸多共性）。 下述表达式是将亡值：

• 返回右值引用类型的函数/重载运算符的返回值；
  
• 向右值引用类型的类型转换（cast）；
  
• 涉及到临时构造一个对象的表达式；
  
• 可移动（move-eligible）的表达式；

1
2
3
4
5
6
7
8
9
10
11
12
13

struct T{int x;};

T func()
{
    int a{};
    int b{std::move(a)}; //std::move(a)产生了一个xvalue表达式

    a = T{}.x; //T{}.x这个表达式整体应视为一个xvalue
    static_cast<int&&>(a); //其实和std::move(a)互为等效

    T b{a};
    return b; //b是move-eligible的，因而这个表达式中b也是xvalue（C++23起）
}

混合类型

“泛左值”和“右值”是两个混合类型（定义见上）。
泛左值(glvalue)的性质有：纯右值性质取反

• 泛左值都可以被转化为纯右值（通过cast等实现）；
  
• 泛左值可以有不完全类型(incomplete type)，并且可以是多态(polymorphic)的；

不完全类：void以及任何未完全定义的类（给出声明但未定义的class、enum (class)、未知长度的数组等）；详见cppreference

多态对象：定义虚函数的类/继承上述类的类 的实例，其特点是会保有一个虚指针(vptr)来实现动态多态性（虚函数调用）以及RTII（运行时类型数据）来辨别其构造时的类型。

“右值”(rvalue)的性质有：左值性质取反

• 右值都不能被取地址（与左值对立，也是判定的充分必要条件）；
  
• 右值都不能被内置的（复合）赋值运算符赋值；（同样地，只看赋值运算符的话既不充分也不必要）
  
• 右值可以用于初始化一个常左值引用/右值引用，此时其生命周期将被延长至与该引用的scope一致(lifetime extension)；
  

  1 2 3 4 5 6 7 8

  int main() { int* ptr = &1; //Not compile: cannot take address of rvalues printf("") = 3; //Not compile: cannot use rvalues as left operand of builtin assignment operators int&& rref = scanf(""); //OK, rvalue initializes rvalue references rref = 5; //OK, lifetime of the return value of scanf() is extended }

• 回顾：右值作为函数参数时，面对rvalue reference和const lvalue reference的重载会优先选择前者（移动语义的实现基础）。

类似地，非const的左值作为函数参数时，面对lvalue reference和const lvalue reference的重载依然会优先选择前者。

const lvalue reference由此也被称为“万金油”，因其可以绑定至任何类型的值上，故可用于实现一层通用的语义（但效率和自由度显然不高）。

右值引用应用之移动语义

何为，何以“移动语义”

移动语义(move sematics)其实不难理解：
类比于现实世界中，我们在搬家时，会希望将自己的很多大件家具都搬到新家，而非在新家购置完全相同的家具并将原家的家具悉数丢弃。
对于C++的对象来说，很多对象都会在创建/运行过程中拥有一些资源（堆内存、文件句柄、线程等等）。
有些时候这些资源的“所有权”可以被直接从一个对象被“转移”至另一个对象，或者用于另一个对象的初始化。而在程序设计中，显然我们会希望区分“允许转移”和“需要复制”这两种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

struct MyVector
{
    int* data;
    size_t size;
};

//转移数据（相当于转移了堆内存的所有权）
void transfer(MyVector& prev,MyVector& cur)
{
    cur.data = prev.data;
    cur.size = prev.size;
    prev.data = nullptr;
    prev.size = 0;
}

//复制数据
void copy(MyVector& prev,MyVector& cur)
{
    cur.size = prev.size;
    cur.data = new int{prev.size};
    for(size_t i=0;i<prev.size;++i)
    {
        cur.data[i] = prev.data[i];
    }
}

在大型程序设计中，我们期望有一个统一的“接口”或“规范”来描述这种语义，即帮助程序设计者解决以下的问题：

• 什么时候一个对象的资源允许被转移？（也就是所谓的can be moved-from，正常情况下一个对象的资源肯定不能被转移，故需要一种统一的“标记”）
  
• 让一个对象被另一个同类对象初始化时，或一个对象被另一个同类对象赋值时（对应的就是特殊的构造函数/赋值运算符），如何决策采取更高效的执行策略（能移动就不要复制一份销毁一份）？
  
• 有些具备“独占性”的对象能否从编译层面来禁止其复制/移动（其占有的资源并不能被复制，如线程或一些大整数/内存的管理类）？

上述问题在C++11前并非无解：比如(3)，C++11前禁止一个对象的复制/移动，可以通过定义一个private的operator=(const Ty&)并不给出实现，在类访问权限/链接设两道“哨兵”。

但显然这种实现方法既不稳妥（如友元类+误定义等等），也有悖于private和不给定义的初衷，且语义不够明确。

移动语义亦然，需要明确的是移动语义只是一个概念，右值及右值引用等为之提供支持（通过重载优先级等帮助在统一的interface下实现），但C++11前并不是无法实现，对于较有限的场景无非是手搓一个函数而已。

C++多用于大型程序编写，开发阶段的要点之一在于保证较高的易读性、可维护性与语义的明确性，这就是右值及右值引用对于移动语义实现的意义。

C++11对左右值概念的强化+右值引用的加入

回到正题，语言层面上规定了对于不同的值，三种不同引用的重载优先级（及可行性）不同。

在任何变量的初始化/赋值操作/函数调用等等中，被传递的永远是值(values)，被操作数（赋值符号左侧、待初始化的变量等等）永远是变量(variables)。

对于 lvalue/rvalue/const lvalue作为值，初始化lref/rref/cref的重载优先级如下：

• 数字越低，优先级越高；若数字不存在，则重载失败。
• 右值引用的核心在于 rvalue 和 rref 的结合优先级高于 cref ，即在遇到接受const Ty&和Ty&&的函数重载时，优先选择后者（即“能移动就不复制”）。
• 同时，rref 胜过 cref 的一点在于前者可以通过引用更改指向对象的状态，而后者不能（需要遵守const语义）

在类的成员函数中，移动语义的实践载体就是函数重载——常见于构造函数和赋值运算符的重载。
传统C++中，对于自定义类Ty，编译器会默认给它加上4个特殊成员函数：（默认）构造Ty::Ty()、复制构造Ty::Ty(const Ty&)、复制赋值Ty::Ty& operator=(const Ty&)、析构Ty::~Ty()。
C++11起特殊成员函数新增了2个，分别为移动构造Ty::Ty(Ty&&)/移动赋值Ty::Ty& operator=(Ty&&)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class CR
{
public:
    CR(){}
    CR(const CR&){} //#1
    CR(CR&&){} //#2
    ~CR(){}
    void modify(){}
};

int main()
{
    CR c{};
    CR d{c}; //Invokes overload #1
    CR e{std::move(c)}; //Invokes overload #2
    
    const CR& ref1 = std::move(d); //binding rvalue to cref
    //ref1.modify(); //Not Compile: const

    CR&& ref2 = std::move(e); //binding rvalue to rref
    ref2.modify(); //OK: non-const

    return 0; 
}

“善后”之被移动对象的处理

“移动”相较传统的“复制-销毁”模式，提出的一个新课题就是如何处理被移动的对象。
C++标准要求被移动的对象应当进入一个valid but unspecified state（有效但未指定状态），具体来说，C++对象在“被移动”后的语义要求分为三层：

• 基本要求：该对象被移动后，调用该对象的析构函数不会抛出异常。在C++这一涉及大量普通变量自动析构的编译期语言中，这点尤为重要。
  一般来说，需要特别明确移动语义的对象都会占有一些资源，为践行 RAII 之原则，其应在析构函数中将获得的资源释放，以防止资源泄露。
  但这时就可能出现资源重复释放的问题，因此基本要求是一个对象被移动后，会将自身的资源标记为“已释放”，从而不会在该对象的生命周期结束时再释放一次，造成异常。
  比如，std::vector<int> 在被移动后会将自己的指针data置为nullptr，如此，在析构函数中执行delete[] nullptr;时就不会发生异常。

热知识：delete/delete[] 一个空指针是合法的语句（什么也不会发生）。

• 标准要求：该对象被移动后，可以被赋值重新使用。C++标准库的容器、对象等均满足这一条件，且标准库对自定义类的封装操作也基于这一假设。

• 更高要求：该对象被移动后，其状态恢复至默认值（犹如被默认构造过一样）。比如std::string被移动后，其将变为一个空字符串；std::thread被移动后将不管理任何线程，与其默认构造后的结果相同。

其实上述要求对于复制构造/复制赋值/移动赋值函数亦然。在传统C++的学习中应当也有涉及到关于编写恰当的复制构造函数，以避免重复释放的相关内容。

不可复制资源的移动——语义归一化

并不是所有的资源/对象都可以被移动/复制。

例如一个thread，线程就不应被移动/复制，一旦开始后只能要么.join()，要么.detach()。
再比如智能指针中的unique_ptr，一个独占型指针的所有权显然不能复制，只能转移。

C++11中，函数的主体可以被声明为= delete;，部分函数（主要是类的6个特殊成员函数，即(默认/复制/移动)构造+(复制/移动)赋值+析构）主体可以被声明为= default;。

若一个函数被声明为= delete;，则该函数不能被调用，否则不能通过编译。一般用于特定参数的函数重载来阻止一些特定参数对函数的调用（一般涉及到隐式转换和重载决议的问题）。

若一个函数被声明为= default;，则编译器将为之生成一个默认的函数。

类的特殊成员函数的默认形式为：

• 默认构造函数，默认构造(default-initialize)每一个数据成员；
• 复制构造函数，复制构造(copy-initialize)每一个数据成员；
• 移动构造函数，移动构造(move-initialize)每一个数据成员；
• 复制赋值运算符，为每一个数据成员进行复制赋值(copy-assignment);
• 移动赋值运算符，为每一个数据成员进行移动赋值(move-assignment);
• 析构函数，析构每一个数据成员。

利用C++11中的语法特性，现在我们可以显式地声明禁用一些默认生成的函数，以此来约束一个类，使之不能被复制/移动/默认构造。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class MoveOnly
{
public:
    MoveOnly() {}
    ~MoveOnly() {}

    MoveOnly(const MoveOnly&) = delete;
    MoveOnly(MoveOnly&&) noexcept {}

    MoveOnly& operator=(const MoveOnly&) = delete;
    MoveOnly& operator=(MoveOnly&&) noexcept {}
};

int main()
{
    MoveOnly a{};
    //MoveOnly b{a}; //Not Compile
    MoveOnly c{std::move(a)}; //OK

    MoveOnly d{};
    //d = c; //Not Compile
    d = std::move(c); //OK
    return 0;
}

C++的名言之一：Rule of Zero/Three/Five 就和默认生成的类的特殊成员函数有关。

其作用对象是 类的默认构造、复制构造、复制赋值、移动构造、移动赋值五个函数。

• Rule of Zero: 若一个类没有定义上述五个函数中的任何一个，那么编译器会为之生成这五个函数的默认形式（见上），亦为我们自定义类时的优先之选。
  
• Rule of Three：若一个类定义了至少一个构造函数，则应该一鼓作气给出全部三个构造函数的定义（所谓的"It almost certainly requires all of three"）。
  
• Rule of Five：若一个类定义了至少一个构造函数和至少一个赋值运算符，则应当一鼓作气给出全部五个函数的定义。

从编译器的角度出发，考虑(三个构造函数/两个赋值运算符)，只要一个类定义了这3(2)个中的一个，该类就不会自动生成剩下2个(1个)构造函数(运算符)。

例外是，若只声明了构造函数（不需是默认构造函数），那么编译器不会再生成默认（无参）构造函数，但依然会生成默认的复制/移动构造函数。

参考以下的代码：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

class A { public: A(int){} }; void fun1() { //A a; //Not Compile: not default constructible A a{1}; A b{a}; //OK, copy ctor still available(default generated) A c{std::move(a)}; //Same with move ctor b = c; //Same with copy assignment operator b = std::move(c); } class B { public: B(const B&) = default; }; void fun2(B& l,B& r) { //B b; //Not Compile(Surprise!) //Upon definition of move/copy ctor, even if the main body is declared as =default, //Default ctor/move ctor is still disabled. //However, assignment operators are still available. l = r; //OK r = std::move(l); //OK } class C { public: C(C&&) = delete; C& operator=(const C&) = delete; }; //Now C is a wasted class that is not constructible nor assignable in any means. //This deprecates the need of defining a fun3():)

移动语义配套语法——引用折叠与完美转发

还是回到那句话：移动语义自身只是一个概念，最终实现在编译期进行，依赖的是函数重载决议。

引用折叠

C++引入右值引用后，template programming中就很可能出现template parameter也是左/右值引用的情况，但C++中又不允许出现引用的引用。
为了保证编程习惯和语义一致，并为后续的移动转发/完美转发做铺垫，提出了引用折叠(reference-collasping)的概念。
具体规则很简单：
考虑一个template参数Ty，其带引用的使用方式可能为左值Ty&及右值Ty&&。
当且仅当Ty是右值引用，且其引用方式也是右值引用Ty&&时，解析结果是右值引用，否则是左值引用。

注意此规则仅在template parameter/using代换中生效，直接写出int&& &&一类的语句仍为非法。

1
2
3
4
5
6
7
8

int x = 1;
using lref = int&;
using rref = int&&;

lref& a = x; //a is l-ref
lref&& b = x; //b is l-ref
rref& c = x; //c is l-ref
rref&& d = std::move(x); //d is r-ref

通用引用和完美转发

既然提到移动语义的实践载体是函数重载，template语境下如何正确地传递（上一个函数携带的参数的）类型信息就显得非常重要。
强化左/右值概念后，为了保证模板实例化代码中依然可以正确地重载左/右值函数，需要对参数的传递做一些额外处理。

C++中，需要注意的是原始形态的具名变量(named variables)一定是左值，无论其属于 lref 还是 rref 。

引用cppreference：Named rvalue references are lvalues; Unnamed rvalue references are rvalues.

如下调用的实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Data{};

void fun(Data&); //#1
void fun(Data&&); //#2

Data foo();

Data data{};
Data&& rref = std::move(data);

fun(data); //Calls overload #1
fun(rref); //Calls overload #1: Named rvalue references are lvalues
fun(Data{}); //Calls overload #2
fun(foo()); //Calls overload #2
fun(std::move(data)); //Calls overload #2: Unnamed rvalue references are rvalues

假设没有通用引用(Universal reference)和完美转发(Perfect Forwarding)的概念，对于一个可能传入左值/右值引用的“中转”函数，至少需要如下两个重载（来保证后续调用语义传递正确）：

1
2
3
4
5
6
7
8
9
10
11
12
13

//左值
template<class Ty>
void fun(Ty& arg)
{
    return foo(arg);
}

//右值
template<class Ty>
void fun(Ty&& arg)
{
    return foo(std::move(arg)); //因为arg虽然是右值引用，但在fun内具名而为左值，必须将之转化回右值
}

同时显然我们也不能“一刀切”地都用std::move传参（不能乱改语义）。
一个参数的情况尚好，但多个参数的重载量将指数级上升；
同时C++11引入了 变长参数模板(variadic templates) 的概念，如果传入的参数中既有左值又有右值，那么Ty&...和Ty&&...两个函数都无法匹配该模板（语法和语义上皆然）。

插播一条C++的模板自动实例化规则：

以参数为int为例，调用fun()时，结合引用折叠的应用——传参为左值时，Ty自动取int&进行实例化；传参为右值时，Ty则取int。

显然叠加右值引用后，二者的参数列表分别为int&和int&&。

如上，这套规则引出了“通用引用”(universal reference)的概念，亦即看到&&不一定就代表右值引用或者逻辑与。
“通用引用”的判定标准为涉及&&+左右值类型推导时，如模板参数中裸露的Ty&&，或函数调用/变量初始化时的auto&&。
通用引用的实现基础依然是引用折叠：

1
2
3
4
5
6
7
8
9
10
11
12

//rref: no type deduction
int&& a = 1; //explicit as it is
Widget&& wgt = Widget{};

template<class Ty>
void bar(std::vector<Ty>&& vec); //不涉及左右值推导，右值

//universal ref: type deduction
auto&& b = a; //b的类型由初始化参数决定，此处由于a是左值，故b的类型为int&
auto&& c = 1; //c是int&&
template<class Ty>
void baz(Ty&& param); //baz同时接受左/右值进行实例化

由此，借助于引用折叠和万能引用，std::forward作为另一个华而不实的"wrapper"来协助实现函数参数左/右值信息的保留。
在需要传递形参作为下一个函数实参的位置，调用std::forward并指定模板实例化参数为Ty，变长参数模板同理：

1
2
3
4
5
6
7
8
9

template<class Ty>
void fun(Ty&& arg) // arg可以是左值，也可以是右值，fun会按需实例化
{
    return foo(std::forward<Ty>(arg)); //std::forward会将类型信息（含左右值）全部保留
}

int x = 1;
fun(x); //Instinates fun(int&) with Ty = int&
fun(1); //Instinates fun(int&&) with Ty = int

与std::move相同，std::forward所执行的依然是编译期的转换，其实现如下。

约定，std::remove_reference_t<Ty> 移除给定类参数Ty的引用信息（左右值皆然），如std::remove_reference_t<int&>即为int。

约定，std::is_lvalue_reference_t<Ty> 测试给定类参数Ty是否为左值引用，如std::is_lvalue_reference_t<int&>为true。

（有关type_traits和SFINAE的坑改天再填.sage）

1
2
3
4
5
6
7
8
9
10
11
12

template<class Ty>
constexpr std::remove_reference_t<Ty>& forward(std::remove_reference_t<Ty>& arg) noexcept
{
    return arg;
}

template<class Ty>
constexpr std::remove_reference_t<Ty>&& forward(std::remove_reference_t<Ty>&& arg) noexcept
{
    static_assert(!std::is_lvalue_reference_t<Ty>,"Bad forward call"); //Cannot forward lvalue as rvalue
    return static_cast<Ty&&>(arg);
}

此处即可看到，std::forward利用了类型信息（所谓Ty）于函数签名中被保留的特点，实现了针对不同左/右值参数的转发——完美转发。

同样地，如果希望实现其它的语义约束，也可以利用引用折叠的规则进行；结合<type_traits>里的各种小组件，搭配自由度更高。
如，C++标准库内置了addressof函数，用于稳定地获取一个对象的地址（即使该类重载了operator&()）。

1
2

template<class Ty>
constexpr Ty* addressof(Ty& arg) noexcept;

通过将参数设置为Ty&，无论Ty取原始类、左值引用还是右值引用，Ty&均会解析为左值引用，使之只能接受左值引用的参数。

实际上这个函数并不完美，标准库实现中还有如下声明以确保不会获取到常右值(const rvalues)的地址：

1 2	template<class Ty> constexpr Ty* addressof(const Ty&&) = delete;

同时，这也是极为少见的 const rvalues/const rrefs 真正地有用武之地的地方（特定场景下的语义/语法约束）。

有关const rvalues 更多探讨可以参考"What are const rvalue references good for?"

类似地可以实现移动转发（将收入的所有参数全部用右值转发出去）：

1
2
3
4
5
6

template<class ...Tys>
constexpr void mov(Tys&&... args)
{
    func(std::forward<Tys>(args)...); //完美转发，保留左/右值属性
    func(std::move<Tys>(args)...); //移动转发，全部转化为右值
}

萍水过客之trivial-types

C++11提出并规范的移动语义，针对的是class/struct的对象。 在此乱世之外，所有的基本数据类型( fundamental types )都是 trivial (“平凡”)的；所有的仅存在平凡数据成员的struct/class也是平凡的。

C++中，<type_traits>中提供了std::is_trivial家族的大量traits用于检验一个类到底有多“平凡”。

定义一个后缀集合 $S = $ {default_constructible,copy_constructible,move_constructible,copy_assignable,move_assignable,destructible}；

std::is_trivially + \(i \in S\) 的traits用于测试一个类是否可以平凡地(默认/复制/移动)构造/(复制/移动)赋值/析构。

trivial 类的特征：

• 其移动语义和复制相同，即移动一个变量后不会改变原对象的数值/状态。
  
• 其构造函数除了初始化数据成员外什么都不做，且其数据成员的初始化也是 trivial 的（递归定义，直至基本数据类型）；复制/移动构造函数同理（只根据原值初始化，不改变其状态）。
  
• 其析构函数除了析构自身数据成员外什么都不做，且其数据成员的初始化也是 trivial 的（同样可以递归定义）。

基本数据类型显然符合这些特点，比如一个int，int的复制/移动只是将自身的值赋予另一个变量，不会影响自身的值；析构一个int什么也不会发生，等等。
显然平凡类的运算是极为高效的（只需要非常“简单”地memset即可完成一切操作，远离移动语义的浮尘喧嚣）。
其引出的问题就是程序的参数设计中传值和传引用之争(挖坑+1)。

移动语义实践中的易错点

“手搓”了不恰当的移动构造函数/赋值运算符

• If you can avoid defining any default operations, do
  
• Use = default if you want to be explicit on using the default sematics
  
• Make move operations noexcept.

• 实践中，对于不直接管理资源的类，尽量避免定义四项默认函数（遵循rule of zero）。
  
• 需要部分地自定义函数时，如需强调使用默认语义/禁止操作，明确写出= default/= delete。
  
• 同时，“手搓”移动构造函数/移动赋值运算符时，尽量声明为 noexcept，否则不能最高效地使用标准库和语言工具。

noexcept也是C++11的新关键字之一（C++11不愧为现代C++之初，全是影响深远的特性），其彻底重塑了C++的异常规范体系（传统C++的throw()异常规范在C++11起被deprecated，并从C++17起彻底移除）。

该关键字既是一个一元编译期运算符(类似sizeof,alignas)，也是一个函数修饰符。

作为编译期运算符时，其接收一个函数作为参数，返回该函数是否可能抛出异常(true/false)，如noexcept(main)即为false（默认状态下）。

作为函数修饰符时，其是函数签名的一部分，并应当追加于其它修饰符之后。如void fun() const noexcept;

修饰方式可以是noexcept(...)其中括号内放编译期可转化为bool的表达式，也可以是noexcept（等价于noexcept(true)）。

对于声明解析为noexcept(true)的函数，其不会向外抛出异常（即不会有任何异常超出该函数的scpoe）。若确有异常超出了其scope，则程序将调用std::terminate。

C++中绝大多数函数默认并没有noexcept(true)，不过析构函数会自动加上noexcept(true)（除非用户主动声明了noexcept(false)）。

但移动构造函数/赋值运算符相对就奇葩些：编译器自动生成（含用户主动声明= default;）的这两个函数会“尽可能地”加上noexcept(true)，但若其某个数据成员的两项函数不是noexcept(true)则不会加上。

如果用户主动定义这两个函数，那么用户需要手动给它加上noexcept(true)的声明。

Every function in C++ is either potentially-throwing or non-throwing.

更多说明可参见cppreference

例如，std::vector在扩容时，会涉及分配新内存和转移已有元素的过程。而C++标准库容器及其方法（成员函数）均满足strong exception guarantee(强异常保证)。

C++函数的异常保证分为四级，降序叙之：

noexcept guarantee > strong exception guarantee > basic exception guarantee > no exception guarantee。

其中，strong exception guarantee的内涵为：调用一个函数时，如果抛出了异常，则所有变量的状态将不发生任何改变（亦即，对变量已经造成的更改可以撤销）。

下面这段代码是对一个递增队列追加元素的函数，要求以'0'结束队列，若序列不是递增的，则抛出异常并遵守strong exception guarantee：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

int append_increment(std::vector<int>& vc) { int temp = 0,count = 0; while(true) { std::cin >> temp; if(!vc.empty() && temp <= vc.back()) //前一个先保证vc不空，卡逻辑短路 { if(temp == 0) { break; } else { vc.push_back(temp); count += 1; } } else { //先执行回滚，擦除所有已写入的数据，再抛异常 vc.erase(vc.end() - count,vc.end()); throw std::runtime_error{"Invalid increment sequence"}; } } return count; }

为了使元素转移的过程满足这个保证，std::vector会使用std::move_if_noexcept检验元素的移动构造函数，在保证转移过程不抛出异常的前提下，效率尽可能地高。
由此，其决策判据及优先级如下：

• 若函数的移动构造函数被声明为noexcept，则使用之（高效；不抛出异常）
  
• 若函数的移动构造函数不可用/未被声明为noexcept，则尝试使用函数的复制构造函数（低效；若复制操作失败（抛出异常），可以回滚）
  
• 若函数的复制构造函数不可用，且移动构造函数未被声明为noexcept，则强异常保证失效（高效；若失败，无法回滚操作）
  
• 若函数的复制/移动构造函数均不可用，则编译失败

故若自定义类的移动构造函数没有被声明为noexcept，则容易导致std::vector在扩容时执行了无用的复制操作，不易发现。

同时，移动语义终究只是一个概念（百听不厌的基本哲学）；最终实现上，依然依靠编写右值引用为参数的代码。
作为反例，我们完全可以实现一个不遵守移动语义的vector，其移动构造函数执行了复制语义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

template<class Ty>
class bad_vec
{
public:
    //其它构造函数等省略
    bad_vec(bad_vec&& from):data{new Ty[from.size]},size{from.size}
    {
        std::copy(from.data,from.data+from.size,this->data);
    }

    bad_vec& operator=(bad_vec&& from)
    {
        this->data = new Ty[from->size];
        this->size = from.size;
        std::copy(from.data,from.data+from.size,this->data);
    }
private:
    Ty* data;
    size_t size;
};

虽然代码可以如此写，编译也没有问题；但如此做进行了复制操作，违背了移动语义的初衷。

从函数return前误移动了局部变量

有时候函数的部分执行分支中，会将某些变量std::move传参到其它函数中，导致了该变量进入了unspecified state。

不能忘记std::move、移动语义、右值引用的初衷：其本质的本质，还是只是一个"tag"，将一个lvalue转化为xvalue。

至于其如何发落，悉数依赖于通过函数签名（形参）重载决策、接受或约束 这些参数的函数。

因此，一行上单纯的std::move(val);语句没有任何意义，不会对val产生任何影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void log(std::vector<int>&& vec)
{
    for(int i : vec)
    {
        std::clog << i;
    }
    vec.clear();
}

void func()
{
    std::vector<int> status{};
    //...

    if(status.size() > 10)
    {
        log(std::move(status));
    } 

    std::cout << status.back() << std::endl; //status may be moved-from
}

上述代码中，log()出于语义约束等考虑选择了只接受右值引用的vector，其在执行后会将vector的内容清空（此操作符合移动语义对被移动对象处理的“更高要求”）。
但func()中，如果不慎进入了if分支，则status将被清空，直接导致其后输出status.back()时抛出异常。
此类调用者的设计“失误”颇为常见（有时是无意为之，有时频繁的move和再赋值/再初始化操作又不可避免）；我们希望避免的是“误移动”而在再初始化前不慎复用之。

防御措施：

• 编译阶段，利用clang-format等静态检查器来标记moved-from变量，对变量潜在的“移动后使用”做好标记；
• 运行阶段，遵循move sematics，每次接受右值引用后将变量的值标记为无效值（比如string的length置零，unique_ptr管理指针赋nullptr），且每次使用一个（潜在的）moved-from变量前检查有效性， 如“官方”教材（摘自cppreference）：

  1 2 3 4 5 6 7 8 9 10

  void func() { std::vector<std::string> v; std::string str = "example"; v.push_back(std::move(str)); // str is now valid but unspecified str.back(); // undefined behavior if size() == 0: back() has a precondition !empty() if (!str.empty()) str.back(); // OK, empty() has no precondition and back() precondition is met str.clear(); // OK, clear() has no preconditions }

其操作原理也非常简单，亦为鲁棒性较好的程序的必备之物：不断地检查preconditions（前置条件）。

return时对返回值是否该std::move辨别失误

一个简单的return语句是整个C++中出现频率最高的语句之一。

为了将其效率发挥到极致，return之争也持续了将近30年，最终在C++23中才勉强画上分号（surprise！连句号都算不上！）。

以下法则仅适用于C++23：

返回move-eligible（可移动）都不应该主动调用std::move，因为这些返回值会被自动视为xvalue（世称implicit move）。
调用std::move将阻碍NRVO(Named return value optimization)。
简而言之，除非已经深得其道，否则可以认为C++23中返回值不需要（也不应该）std::move(local_variable)。

简单来说，具有自动存储周期(automatic storage duration)的非volatile、非左值引用变量都是move-eligible 的。除了static,thread_local以外常用的变量皆然（含右值引用变量）。

如下函数在C++23前返回悬挂引用(dangaling reference)，C++23起其非良构(ill-formed)而不能通过编译。当然你如果把返回值改成rref那还是可以返回悬挂引用的

1
2
3
4
5

int& ret()
{
    int x = 1;
    return x; //Not compile: invalid binding(x is a xvalue in this context)
}

即使是返回move-only的对象，同样可以直接return，不加任何修饰：（在C++20必须写作std::move(ref)，C++20起将右值引用划归move-eligible 因而可以通过）

1
2
3
4
5

std::unique_ptr<int> fun(std::unique_ptr&& ref)
{
    //...
    return ref; 
}

结语

C++11作为现代C++的开山之作，其带来的极大量新语法、新关键字、新概念等极为庞大，移动语义即为其间数“巨头”之一。
学习移动语义，理论学习的吸收难度已然颇大；但更难、同时也让学习之变得更有意义的是在现代C++的编程实践中积极运用，使自身程序设计的质量、效率更高。
同时，尝试理解、融会贯通其间涉及C++的诸多设计哲学，亦会对学习、生活、工作受益匪浅。

望能与各位道友在求道之路上共勉。

离散对数问题，Discrete Logorithm Problem，简称DLP，是非对称密码学所依赖的极为重要的数学难题之一。
经典DLP问题描述：
给定 \(g^x \equiv c (mod p) （g,x < p）\)，由 \((g,x)\) 计算 \(c\) 很容易（快速幂取模），但由 \((g,c)\) 计算 \(x\) 是困难的。

即使是BSGS等攻击方法，依然必须涉及“爆破”一步，即在x的可能范围内逐个数值尝试是否能让等式成立。

离散数学（广义上）DLP问题描述： 设循环群 \(G_p\) 的阶为 \(n\)。
给定群内的任意元素 \(A \in G_p\) 及 \(x < n\)，计算 \(C = x \cdot A\) 很容易，但给定 \(C\)、\(A\)，求解 \(x\) 是困难的。
这里x代表A执行二元运算的次数，对于经典DLP，其为模p环下的乘法运算；对于ECDLP，其为椭圆曲线上的加法运算。

给定\(C,x\)，可以计算 \(A = x^{-1} \cdot C\)，此时 \(x^{-1}\) 应理解为 \(x\) 在 \(Zmod(n)\) 下的逆元。

由DLP问题衍生出的 Diffle-Hellman 密钥交换：
假设Alice和Bob希望在一个不安全的环境下进行密钥交换。他们协商密钥交换在 \(G_p\) 上进行，选定生成元 \(G\) 并公开。
Alice和Bob分别产生一个私钥 \(d_A\) 和 \(d_B\)，分别计算 \(A = d_A \cdot G\) 与 \(B = d_B \cdot G\)，将 \(A\)、\(B\) 发送给对方并公开。
随后，他们再分别使用私钥和对方发送的密钥计算 \(AB = d_A \cdot B = d_B \cdot A\)。 在阿贝尔群上其正确性显然。
此时双方就已经完成了密钥交换，共享密钥就是AB。外人即使知道了 \((G_p,G,A,B)\)，亦很难从中获得\(d_A\)或\(d_B\)，进而保证了共享密钥 \(AB\) 的安全性。

攻击方法概览

• 暴力攻击，在n较小时，攻击者可以枚举所有的 \(x \in (0,n)\) 逐个校验。
  
• BSGS(Baby-step Giant-step，大步小步法，又名“亦步亦趋”)，通过制造碰撞来“用空间换时间”。

大步小步法的空间复杂度与时间复杂度均为 \(O(\sqrt n)\)。暴力攻击的二者显然分别为 \(O(1)\) 及 \(O(n)\)。

• Pohlig-Hellman攻击
  
• Pollard's kangaroo algorithm
  
• Pollard's rho algorithm

上述是较为通用的解法，对于部分 \(G_p\) 存在特有的攻击方法，比如ECDLP下的Smart's Attack、MOV Attack等。

另外，有一些循环群可能求解 \(G_p\) 上的离散对数问题并不困难，比如 \(Zmod(p)\) 上的加法运算可以快速求解。

细讲

以下内容干货（纸面资料）过多，小心噎着

BSGS —— 亦步亦趋

BSGS本质是在试着制造碰撞，利用散列表查找复杂度为常量的优势，以空间换时间。
具体操作方法如下：设待求解 \(C = x \cdot G\) 中的x，
记 \(T = \sqrt n\)，\(R = G \cdot T^{-1}\)；制备一个散列表集合 \(S = {i \cdot G}，i \in [0,C)\)
随后遍历 \(j \in [0,C)\)，若 \(C + j \cdot R \in S\) ，则说明碰撞成功，得到 \(x = jT + i\)。
显然遍历中一定会存在一次碰撞。

“大步小步”的命名之源：

如上式，\(i\) 每增加1，\(x\) 增加1，所谓一“小步”；\(j\) 每增加1， \(x\) 增加 \(\sqrt n\) ，所谓一“大步”。

这种攻击思想在轮加密/类轮加密的攻击（含哈希碰撞）中也有较多应用，思路即为将密钥拆为两部分，将中间值进行碰撞。

为了便于理解，给出一段示意BSGS求解 \(GF_p\) 下DLP问题的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def dlog(p:int,c:int) -> int:
    g = 2 #假设目标是求解pow(2,x,p)==c中的p
    t = int(pow(p,1/2))
    r = pow(2,-t,p)

    dc = {}
    for i in range(t):
        dc[g] = i
        g = (g * 2) % p
    
    for j in range(t):
        if c in dc: #找到碰撞
            return dc[c] + j * t
        c = (c * r) % p

    return None

Pohlig-Hellman —— 韩信点“兵”

Pohlig-Hellman 利用了群论中的拉格朗日定理和中国剩余定理。
其攻击对象是阶的小因子之积过小的循环群，在这些群上，可以求解(部分)阶比较小的子群的离散对数问题；
对这些结果应用中国剩余定理，即可获得原群上离散对数问题的结果。

群中的拉格朗日定理：如果 \(G_P\) 是 \(G\) 的一个子群，则 \(ord(G_P)\) 一定整除 \(ord(G)\)。

攻击成立的两个场景：
- 目标群的阶的全部因子都很小，a.k.a.“光滑数”(smooth-number)；
- 目标运算数计数 \(x\) 小于目标群的阶的小因子之积（实际上第一种情况可以看作是第二种情况的特例）。

实现上，我们令 $n = $ \(\prod_{i=1}^m{p_i^{e_i}}\)。对于每个因子 \(f = p_i^{e_i}\)，考虑 \(C^{'} = f \cdot C\)，\(G^{'} = f \cdot G\)。
此时 \(C^{'}\) 在群中的阶为 \(\frac{n}{f}x\)，\(G^{'}\) 的阶则为 \(\frac{n}{f}\)。
根据拉格朗日定理，此时以 \(G^{'}\) 为生成元的子群的阶只有 \(f\)，且 \(C^{'}\) 亦在这个群上，故可以在这个低阶子群上求解DLP。
依此法求解的 \(\{x_i\}\) 满足 \(x_i \equiv x (mod p_i^{e_i})\)。

• 对于第一种情况，显然 \({p_i^{e_i}}\) 互素，故将所有等式联立至CRT中，求出通解 \(x^{'} = x_0 + kn'\)，令 \(k=0\) 即可获得 \(x\)。
  
• 对于第二种情况，假设存在 \(x < r\)，则可以升序求解模 \(p_i^{e_i}\) 下的DLP，只需要求解出的 \(\prod_{i=1}^m{p_i^{e_i}} > r\) ，即可令CRT求解出的 \(x^{'}\) 模数大于 \(r\)，进而获得 \(x\)。

还是直接上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def ph_attack(p:int,c:int,intact: bool = True) -> int: #仍旧是pow(2,x,p) == c
    g = 2
    
    #约定，factor(x)返回一个list，每个元素是形如(prime,factor)的tuple
    #约定，预置了discrete_log(a,g)返回int，作用为给定(g,a)，求解群中满足a = x * g的x，其可以采用暴力攻击、BSGS等方法进行
    #约定，函数crt(r,m)可以对给定两个等长的列表，且m各元素互质时，求CRT问题的基础解(k=0)
    rls = []
    mls = []

    n = p - 1 #Zmod(p)的阶

    #对于第一种情况的攻击，即不知道x的额外信息，完全攻击每个子群
    if intact:
        for pm,exp in factor(n):
            cur = pow(pm,exp)
            fc = n // cur
            temp_g = pow(g,fc,p)
            temp_c = pow(c,fc,p)
            mls.append(cur)
            rls.append(discrete_log(temp_c,temp_g))

    #对于第二种情况的攻击，攻击部分子群，其实只需要记录已经求解的模数之积，伺机break
    else:
        Sentinel = pow(2,32) #x的上界
        mul = 1
        for pm,exp in factor(n):
            cur = pow(pm,exp)
            fc = n // cur
            temp_g = pow(g,fc,p)
            temp_c = pow(c,fc,p)
            mls.append(cur)
            rls.append(discrete_log(temp_c,temp_g))
            mul *= cur
            if mul > Sentinel:
                break

    return crt(rls,mls)

因此，为使任意场景实例化的DLP问题抵抗Pohlig-Hellman攻击，该群的阶或应没有小因子（最好阶自身就是大质数），或其小因子极少且乘积极小。

对于 \(Zmod(p)\) 上的离散对数问题，一般会要求p是质数的同时，\(\frac{p-1}{2}\) 为质数（或没有小因子）。

\(p\) 是质数时，其阶 \(\phi(p) = p-1\)，显然此时 \(2\) 是其阶的一个因子，令其阶的另一个因子是质数，同时约束 \(x>2\)，即可确保其最大限度地抵抗Pohlig-Hellman攻击。

只要一个群的阶不是质数，那么Pohlig-Hellman总能通过转而攻击子群，降低求解该群上DLP问题的复杂度。

sagemath中内置了求解离散对数相关的工具：

1
2
3
4
5
6
7
8
9
10
11
12
13

#sage
p = 7
E = EllipticCurve(Zmod(p),[0,2])
A = E.random_point()
G = E.gens()[0]

#经典调用方法，discrete_log是一个通用化的函数，第一参数为结果，第二参数为底，内置方法就是Pohlig-Hellman和BSGS

#指定operation相当于约定了特定的运算（对于EllipticCurve默认为'+'，对于Zmod(p)默认为'*'）
print(discrete_log(A,G,operation='+')) 

#还可以指定bounds=(a,b)来引导sage来利用上述Pohlig-Hellman攻击中的第二种情况
print(discrete_log(A,G,operation='+',bounds=(0,5))) #假设x的上界为5