Eduardo P C Rocha
email: eduardo.rocha@pasteur.fr

David Bikard

Microbial defenses against mobile genetic elements and viruses: Who defends whom from what?

Keywords: HGT, horizontal gene transfer, ICE, integrative conjugative element, MGE, mobile genetic element

Prokaryotes have numerous mobile genetic elements (MGEs) that mediate horizontal gene transfer (HGT) between cells. These elements can be costly, even deadly, and cells use numerous defense systems to filter, control, or inactivate them. Recent studies have shown that prophages, conjugative elements, their parasites (phage satellites and mobilizable elements), and other poorly described MGEs encode defense systems homologous to those of bacteria. These constitute a significant fraction of the repertoire of cellular defense genes. As components of MGEs, these defense systems have presumably evolved to provide them, not the cell, adaptive functions. While the interests of the host and MGEs are aligned when they face a common threat such as an infection by a virulent phage, defensive functions carried by MGEs might also play more selfish roles to fend off other antagonistic MGEs or to ensure their maintenance in the cell. MGEs are eventually lost from the surviving host genomes by mutational processes and their defense systems can be co-opted when they provide an advantage to the cell. The abundance of defense systems in MGEs thus sheds new light on the role, effect, and fate of the so-called "cellular defense systems," whereby they are not only merely microbial defensive weapons in a 2-partner arms race, but also tools of intragenomic conflict between multiple genetic elements with divergent interests that shape cell fate and gene flow at the population level.

Introduction: Mobile genetic elements drive gene flow at a (sometimes hefty) cost

Horizontal gene transfer (HGT) allows bacteria and archaea to rapidly match novel ecological challenges and opportunities. HGT is most frequently mediated by mobile genetic elements (MGEs) like bacteriophages (phages) and conjugative elements that are present in most genomes, often in multiple copies (for definitions, see Box 1). These elements can autonomously transfer themselves from one cell to another using viral particles or conjugative pili, processes that also contribute to the exchange of chromosomal DNA. Besides their ability to drive HGT, many MGEs encode traits adaptive to the host cell. For example, key virulence factors in many human pathogens are encoded in prophages, and the transfer of antibiotic Box 1. Glossary.

Abortive infection: process by which an infected cell induces its own death before the phage can complete its replication cycle. This strategy is employed by a large diversity of defense systems that sense infection and trigger cell death through various mechanisms.

Allelic recombination: a process, usually using homologous recombination, which results in allelic exchanges between very similar genes present in different genomes. One uses the term recombination for exchanges leading to transfer of polymorphism in conserved genes (gene conversion) from one bacterium to another and HGT for transfer of novel genes.

Balancing selection: evolutionary process where there is selection to maintain polymorphism in the population. For example, it can favor the diversity of alleles in genomes (e.g., multiple polymorphic copies of a gene family in a genome), the preservation of rare alleles in populations (negative frequency-dependent selection selection), or of different alleles in different environments or different moments.

Chromosome hotspots: regions of bacterial chromosomes with high turnover of genetic material, i.e., with frequent insertion and deletion of genes acquired by HGT (often in MGEs).

Conjugative elements: plasmids or integrative conjugative elements (ICEs) can produce a mating pair formation structure at the cell envelope to transfer DNA between neighboring cells.

Clustered regularly interspaced short palindromic repeats/CRISPR associated protein (CRISPR/Cas) systems: provide adaptive immunity based on spacer sequences within CRISPR arrays. These sequences guide nucleases to destroy cognate invading genetic elements.

Defense islands: chromosomal loci with high density of defense systems.

Homologous recombination: molecular process that results in the joining of two DNA molecules at a region of homology. Can result in the exchange of polymorphism between the chromosome and exogenous DNA sequences.

Horizontal gene transfer (HGT): transfer of novel genes from one microbial cell to another.

Mobile genetic elements (MGEs): semiautonomous genetic elements that are capable of mobility within or between genomes. They include phages and conjugative elements capable of autonomous transfer between cells, satellites and mobilizable elements capable of hijacking the former ones, and many other elements whose means of horizontal transfer are unknown.

Mobilizable elements: plasmids or integrative mobilizable elements (IMEs) capable of hijacking mating pore formation structures of conjugative elements for their own transfer.

Phages: bacterial viruses.

Phage satellites: MGEs capable of hijacking phage particles produced by phages for their own transfer. resistance genes is driven by conjugative elements [START_REF] Taylor | The diverse impacts of phage morons on bacterial fitness and virulence[END_REF][START_REF] Bennett | Plasmid encoded antibiotic resistance: acquisition and transfer of antibiotic resistance genes in bacteria[END_REF]. By increasing the host fitness in specific contexts, these traits contribute to the proliferation of MGEs in communities, i.e., they directly contribute to MGE fitness. In other contexts, these traits can be costly and, together with the costs of vertical and horizontal transfer, lower the host fitness [START_REF] Baltrus | Exploring the costs of horizontal gene transfer[END_REF]. As a result of these costs, MGEs rarely remain in genomes for long periods of time [START_REF] Croucher | Horizontal DNA transfer mechanisms of bacteria as weapons of intragenomic conflict[END_REF], and different strains tend to carry very different repertoires of prophages, plasmids, or transposable elements [START_REF] Touchon | Causes of insertion sequences abundance in prokaryotic genomes[END_REF][START_REF] Toro | Plasmid diversity and adaptation analyzed by massive sequencing of Escherichia coli plasmids[END_REF][START_REF] Bobay | Pervasive domestication of defective prophages by bacteria[END_REF][START_REF] Hussain | Rapid evolutionary turnover of mobile genetic elements drives bacterial resistance to phages[END_REF].

Conjugative elements and phages also have molecular parasites that use their mechanisms of horizontal transmission to transfer between cells. For example, viral particles produced by phages can be hijacked by phage satellites [START_REF] Penade ´s | The phage-inducible chromosomal islands: a family of highly evolved molecular parasites[END_REF], and conjugative pili can be used by so-called mobilizable elements [START_REF] Smillie | Mobility of Plasmids[END_REF]. Many other MGEs lack known mechanisms of horizontal transmission and may transfer between cells by exploiting phages and conjugative elements [START_REF] Smillie | Mobility of Plasmids[END_REF]. It must be noted that the presence of a MGE affects the frequency of other MGEs in the cell. This is the case of the mobility of multiple conjugative plasmids in cells [START_REF] Gama | Multiple plasmid interference-Pledging allegiance to my enemy's enemy[END_REF], of the abovementioned mobilizable plasmids and phage satellites that cotransfer in synchrony with conjugative elements and phages, and of phages that use the conjugative pilus as a receptor for cell infection [START_REF] Harb | ssRNA phage penetration triggers detachment of the F-pilus[END_REF]. Finally, infection by a MGE may spur the transfer of others. Phage infection favors the transfer of SXT-like integrative conjugative elements (ICEs) [START_REF] Legault | Temporal shifts in antibiotic resistance elements govern virus-pathogen conflicts[END_REF] and conjugation-induced SOS response activates MGEs in the recipient cells [START_REF] Baharoglu | Conjugative DNA transfer induces the bacterial SOS response and promotes antibiotic resistance development through integron activation[END_REF]. Transposable elements are a particularly important family of mobile elements that is very abundant within other MGEs and facilitates genetic exchanges between them and with the host [START_REF] He | Mechanisms of evolution in high-consequence drug resistance plasmids[END_REF]. The cellular genome thus harbors a large diversity of MGEs establishing complex interactions among each other and with the host cell.

The associations between the host and its MGEs lay on a continuum going from pure parasitism to intimate mutualism because vertical and horizontal transmission of MGEs impose fitness costs to the cell that may eventually be outweighed by advantageous traits encoded by them. Virulent phages are at the edge of maximal virulence in this continuum since their successful infection implicates cell death. The fitness effects of the remaining MGEs, and of the accessory traits they encode, are more diverse and vary with the physiological state of the cell and the presence of competing MGEs. Temperate phages are striking examples of such ambiguity. Their integration in the genome can provide novel adaptive traits [START_REF] Wagner | Bacteriophage control of bacterial virulence[END_REF], but their subsequent excision from the genome usually ends in host death [START_REF] Paul | Prophages in marine bacteria: dangerous molecular time bombs or the key to survival in the seas?[END_REF]. The richness of the interactions between MGEs and the host make their impact contingent on a specific cellular context, i.e., this impact varies with the strain genetic background. MGEs that are parasites of other MGEs impact the fitness of the latter. If this impact is very high and the parasitized MGE is deleterious to bacteria, then the parasite of the parasite benefits the host cell. For example, some satellites can abolish phage transmission by release of viral particles exclusively packaged Restriction-modification (R-M) systems: use specific methylation patterns to distinguish self from nonself. Incoming MGEs lacking compatible methylation patterns are degraded by a nuclease.

Retron: genomic elements encoding a reverse transcriptase and a noncoding RNA that is partly reverse transcribed to form a RNA-DNA hybrid. Some retrons have been recently shown to be antiphage defense systems.

Transduction: processes by which phage particles transfer bacterial DNA between cells.

with the satellite genome [START_REF] Seed | A bacteriophage encodes its own CRISPR/Cas adaptive response to evade host innate immunity[END_REF]. Although this process still ends in cell death, the inhibitory effect of the satellite on phage reproduction blocks its epidemic growth, thereby protecting the microbial population. Since most genomes contain plasmids, prophages, and other MGEs [START_REF] Smillie | Mobility of Plasmids[END_REF][START_REF] Touchon | Genetic and life-history traits associated with the distribution of prophages in bacteria[END_REF], and virulent phages are extremely abundant in the environment [START_REF] Wigington | Re-examination of the relationship between marine virus and microbial cell abundances[END_REF], the fate of cells often hangs in the outcome of their interaction with MGEs and that of MGEs among themselves.

The potential for conflicts in the interactions between MGEs and the host led to the evolution of defense mechanisms to filter, control, or inactivate them [START_REF] Van Houte | Evolutionary ecology of prokaryotic immune mechanisms[END_REF][START_REF] Hampton | The arms race between bacteria and their phage foes[END_REF]. These systems are now being unraveled at fast pace even though their mechanisms are in many cases still poorly understood [START_REF] Doron | Systematic discovery of antiphage defense systems in the microbial pangenome[END_REF][START_REF] Gao | Diverse enzymatic activities mediate antiviral immunity in prokaryotes[END_REF]. The extensive description of these systems falls outside the scope of this text and can be found elsewhere [START_REF] Gonza ´lez-Delgado | Prokaryotic reverse transcriptases: from retroelements to specialized defense systems[END_REF][START_REF] Bernheim | The pan-immune system of bacteria: antiviral defence as a community resource[END_REF][START_REF] Lopatina | Abortive infection: bacterial suicide as an antiviral immune strategy[END_REF][START_REF] Nussenzweig | Molecular mechanisms of CRISPR-Cas immunity in bacteria[END_REF]. Some defenses are part of core cellular systems and provide protection from MGEs as part of a broader set of cellular functions (Fig 1). For example, RecBCD is a powerful exonuclease involved in the repair of double-strand breaks by homologous recombination. It degrades linear double-stranded DNA until it meets a Chi site beyond which it loads the recombinase RecA. Phages lacking Chi sites are rapidly degraded by the enzyme [START_REF] Cheng | A conformational switch in response to Chi converts RecBCD from phage destruction to DNA repair[END_REF]. The resulting DNA can be recovered by other defense systems, like clustered regularly interspaced short palindromic repeats/CRISPR associated protein (CRISPR/Cas) or the Argonaut, to build more specific defenses against subsequent infections by the same phages [START_REF] Levy | CRISPR adaptation biases explain preference for acquisition of foreign DNA[END_REF][START_REF] Kuzmenko | DNA targeting and interference by a bacterial Argonaute nuclease[END_REF]. Hence, generic defense systems that are part of the host core genome may nourish more specialized systems for more specific protection. Interestingly, Lambdoid phages in Escherichia coli either lack Chi sites, in which case they usually encode anti-RecBCD systems to block RecBCD and produce their own recombination systems, or have many Chi sites and use the host homologous recombination machinery for their own replication [START_REF] Bobay | Manipulating or superseding host recombination functions: a dilemma that shapes phage evolvability[END_REF]. Bacteria have evolved responses to protect themselves from phage-encoded anti-RecBCD systems. A retron was recently discovered that induces cell death when the RecBCD function is compromised, i.e., the retron is a guardian of RecBCD and has a protective anti-anti-RecBCD function [START_REF] Millman | Bacterial retrons function in anti-phage defense[END_REF].

Contrary to RecBCD, many defense systems are not involved in core cellular processes. Instead, they are specialized in providing innate or adaptive immunity. Restriction-modification (R-M) systems, by far the most abundant defense systems in bacterial genomes [START_REF] Oliveira | The interplay of restriction-modification systems with mobile genetic elements and their prokaryotic hosts[END_REF][START_REF] Tesson | Systematic and quantitative view of the antiviral arsenal of prokaryotes[END_REF], provide excellent illustrations of the evolutionary processes resulting in the evolution of defense and counter-defense systems (Fig 1). They imprint epigenetically the cellular genome and inactivate (restrict) infecting MGEs lacking the adequate DNA modifications. As a response, some phages counteract the activity of R-M systems by either producing antirestriction proteins or by extensively modifying their DNA [START_REF] Isaev | Phage T7 DNA mimic protein Ocr is a potent inhibitor of BREX defence[END_REF][START_REF] Kru ¨ger | Multiple mechanisms for avoiding the deoxyribonucleic acid restriction systems of their hosts[END_REF]. Anti-restriction functions can, in turn, be recognized by bacterial anti-anti-restriction systems that provide a second layer of resistance when R-M fails, e.g., by inducing cell death (abortive infection, Fig 1) [START_REF] Rousset | Prophage-encoded hotspots of bacterial immune systems[END_REF]. As a complement, phages with extensive modifications in their DNA can be recognized by specific bacterial antimethylation restriction systems [START_REF] Fukuda | Cell death upon epigenetic genome methylation: a novel function of methyl-specific deoxyribonucleases[END_REF][START_REF] Loenen | The other face of restriction: modification-dependent enzymes[END_REF]. The evolution of this tit-for-tat mechanisms can go very far. For example, phage T4 encodes an anti-restriction system that can be recognized by hosts encoding an anti-anti-restriction system that induce cell death by tRNA cleavage. This abortive infection system can be canceled by T4 because it can repair the cleaved tRNAs using a pair of proteins that constitute an anti-anti-anti-restriction system [START_REF] Penner | Phage T4-coded Stp: double-edged effector of coupled DNA and tRNA-restriction systems[END_REF].

Defense and counter-defense systems are often studied in the light of the antagonistic interaction between one host and a virulent phage. But the reality is much more complex and interesting because many of the systems found in bacterial genomes and once thought to be dedicated to the defense of the cell are actually encoded in MGEs. This includes systems encoded in temperate phages [START_REF] Hussain | Rapid evolutionary turnover of mobile genetic elements drives bacterial resistance to phages[END_REF][START_REF] Bondy-Denomy | Prophages mediate defense against phage infection through diverse mechanisms[END_REF][START_REF] Dedrick | Prophagemediated defence against viral attack and viral counter-defence[END_REF][START_REF] Piel | Genetic determinism of phage-bacteria coevolution in natural populations[END_REF][START_REF] Owen | Prophages encode phage-defense systems with cognate self-immunity[END_REF], satellites [START_REF] Rousset | Prophage-encoded hotspots of bacterial immune systems[END_REF][START_REF] Mckitterick | Anti-phage islands force their target phage to directly mediate island excision and spread[END_REF][START_REF] Fillol-Salom | Beyond the CRISPR-Cas safeguard: PICI-encoded innate immune systems protect bacteria from bacteriophage predation[END_REF], conjugative elements [START_REF] Legault | Temporal shifts in antibiotic resistance elements govern virus-pathogen conflicts[END_REF][START_REF] Klaenhammer | Plasmid-directed mechanisms for bacteriophage defense in lactic streptococci[END_REF][START_REF] Pinilla-Redondo | Type IV CRISPR-Cas systems are highly diverse and involved in competition between plasmids[END_REF][START_REF] Leo ´n | Mobile element warfare via CRISPR and anti-CRISPR in Pseudomonas aeruginosa[END_REF], mobilizable plasmids [START_REF] Oliveira | The interplay of restriction-modification systems with mobile genetic elements and their prokaryotic hosts[END_REF], and genomic islands acquired by HGT [START_REF] Hussain | Rapid evolutionary turnover of mobile genetic elements drives bacterial resistance to phages[END_REF][START_REF] Piel | Genetic determinism of phage-bacteria coevolution in natural populations[END_REF][START_REF] Avrani | Genomic island variability facilitates Prochlorococcus-virus coexistence[END_REF]. For example, defense systems in Vibrio and in other species are a significant part of the species' accessory genome (12% to 20%) and are very frequently encoded in MGEs, many of which are poorly known [START_REF] Hussain | Rapid evolutionary turnover of mobile genetic elements drives bacterial resistance to phages[END_REF]. It is important to note that the presence of occasional defense systems in phages or plasmids has been known for decades. What these recent observations highlight is that a large fraction of the so-called cell defense systems are encoded in MGEs. This raises intriguing questions concerning the role, function, and evolution of the so-called cellular defense systems (Fig 2 ).

Why are there so many defense systems in each genome?

Most bacterial genomes encode several R-Ms, but often also CRISPR/Cas, retrons, and many other defense systems [START_REF] Tesson | Systematic and quantitative view of the antiviral arsenal of prokaryotes[END_REF]. For example, the first 2 sequenced genomes of Helicobacter pylori encode a total of more than 20 putative R-M systems [START_REF] Lin | Comparative genomics of the restriction-modification systems in Helicobacter pylori[END_REF], and genomes with multiple CRISPR arrays and Cas systems are frequent [START_REF] Bernheim | Atypical organizations and epistatic interactions of CRISPRs and cas clusters in genomes and their mobile genetic elements[END_REF]. The fast pace of discovery of novel defense and counter-defense systems suggests that they may account for a significant number of the unknown function genes in genomes. The numerous defense systems of some genomes protect the cell from a broad range of MGEs, counteracting the latter's tendency to evolve counter-defenses. It could also facilitate building up multiple layers of cell defenses that may culminate in cell death when all else fails [START_REF] Lopatina | Abortive infection: bacterial suicide as an antiviral immune strategy[END_REF]. In this view, cell defense systems are numerous because they make a multilayered immune system to tackle different elements. Yet, defense systems can be costly [START_REF] Bondy-Denomy | To acquire or resist: the complex biological effects of CRISPR-Cas systems[END_REF], because of production costs when they are required at high concentration [START_REF] Vale | Costs of CRISPR-Cas-mediated resistance in Streptococcus thermophilus[END_REF], because their activity can be energetically costly [START_REF] Seidel | Motor step size and ATP coupling efficiency of the dsDNA translocase EcoR124I[END_REF], or because they may be incompatible with other cellular mechanisms [START_REF] Bernheim | Inhibition of NHEJ repair by type II-A CRISPR-Cas systems in bacteria[END_REF]. They can also kill the cell by autoimmunity [START_REF] Rollie | Targeting of temperate phages drives loss of type I CRISPR-Cas systems[END_REF]. Hence, the number of systems under selection for defense by the host cell is expected to depend on the balance between these costs and the rewards given by their ability to protect hosts from MGEs.

The observations that genomes have many MGEs and that these encode many defense systems provide an alternative or complementary explanation for why genomes contain so many such systems. Genomes contain many defense systems because they are acquired within the multiple MGEs that infect microbial cells. Since there are many MGEs in a cell, these sum up to a considerable number of defense genes. Such MGE-encoded defenses may also be multilayered. For example, E. coli plasmids encoding both BREX and type IV restriction systems have recently been shown to provide complementary protection from phages [START_REF] Picton | The phage defence island of a multidrug resistant plasmid uses both BREX and type IV restriction for complementary protection from viruses[END_REF]. This does not exclude the possibility that cells select for multiple systems of defense, but does suggest that to understand their frequency in cells one must also account for the infectivity of MGEs. This means that the multiplicity of systems in cellular genomes might be a consequence of the high transmissibility and abundance of MGEs, not (only) the result of natural selection for protection of the cell. It is therefore possible that cells encode more defense systems than the theoretical optimal number expected for a host cell, simply because many of the systems are selected for their presence in the MGE, not in the host.

Why are defense systems very diverse within species?

Defense systems tend to be different across strains of a species [START_REF] Van Houte | Evolutionary ecology of prokaryotic immune mechanisms[END_REF][START_REF] Avrani | Genomic island variability facilitates Prochlorococcus-virus coexistence[END_REF] and are a significant part of the genetic differences between closely related strains of Vibrio spp. [START_REF] Hussain | Rapid evolutionary turnover of mobile genetic elements drives bacterial resistance to phages[END_REF]. Why are defense systems so different among strains of a species? The coevolutionary dynamics between defenses and counter-defenses contributes to an endless process of genetic diversification that is often understood in the context of balancing selection [START_REF] Fijarczyk | Detecting balancing selection in genomes: limits and prospects[END_REF]. These are processes where natural selection favors the existence of genetic polymorphism. Interestingly, balancing selection resulting in the presence of diverse defense systems in populations is observed in many immune systems, from bacteria to humans [START_REF] Woolhouse | Biological and biomedical implications of the co-evolution of pathogens and their hosts[END_REF]. Defense and antidefense systems are often studied in the context of the interaction between one host and one MGE, usually a virulent phage (left). Yet, the presence of numerous MGEs in populations and their ability to encode their own defense systems renders the picture more complex (right). Virulent phages establish antagonistic interactions with the other MGEs and the cell [START_REF] Taylor | The diverse impacts of phage morons on bacterial fitness and virulence[END_REF]. But the associations between the other MGEs and the cell can be more diverse (2 to 7). Temperate phages and conjugative plasmids exploit their cellular host (2 and 4) and can be exploited by other MGEs (3 and 5). Plasmids often encode systems that are effective barriers to phages, e.g., R-M [START_REF] Toro | Plasmid diversity and adaptation analyzed by massive sequencing of Escherichia coli plasmids[END_REF]. Phages are a threat to plasmids when they kill the host cell [START_REF] Toro | Plasmid diversity and adaptation analyzed by massive sequencing of Escherichia coli plasmids[END_REF]. Satellites may benefit the host by diminishing phage infection [START_REF] Bobay | Pervasive domestication of defective prophages by bacteria[END_REF]. Most of these interactions (2 to 8) can at times be beneficial to both partners, e.g., when a conjugative plasmid provides a nosocomial bacterium with antibiotic resistance. MGE, mobile genetic element. https://doi.org/10.1371/journal.pbio.3001514.g002

Balancing selection can occur by multiple mechanisms. First, it is harder for a parasite to spread in a population with diverse host defenses even in simple systems [START_REF] Chabas | Evolutionary emergence of infectious diseases in heterogeneous host populations[END_REF]. For example, genetic diversity in the host CRISPR/Cas spacers that target a phage favor the host and make the mutational escape by the phage more difficult [START_REF] Van Houte | The diversitygenerating benefits of a prokaryotic adaptive immune system[END_REF]. The presence of various systems providing immunity from MGEs within microbial populations increases the likelihood that some individuals are protected, in what has been described as distributed (pan) immunity [START_REF] Bernheim | The pan-immune system of bacteria: antiviral defence as a community resource[END_REF]. Relative to microbial genomes, MGEs are more constrained in the number of genes they can carry, especially those packaged in viral particles. Yet, some also carry multiple defense systems [START_REF] Hussain | Rapid evolutionary turnover of mobile genetic elements drives bacterial resistance to phages[END_REF][START_REF] Legault | Temporal shifts in antibiotic resistance elements govern virus-pathogen conflicts[END_REF][START_REF] Rousset | Prophage-encoded hotspots of bacterial immune systems[END_REF][START_REF] Piel | Genetic determinism of phage-bacteria coevolution in natural populations[END_REF], which may allow them to infect different hosts or fend off different MGEs.

Second, variations in time and space of the density, type, and behavior of MGEs may favor different cellular defense systems in different situations. The distribution of MGEs varies across bacterial habitats [START_REF] Brito | Mobile genes in the human microbiome are structured from global to individual scales[END_REF] and across environmental conditions within habitats [START_REF] Diard | Inflammation boosts bacteriophage transfer between Salmonella spp[END_REF]. Hence, locally adapted microbial populations may select for different systems that tackle different types of MGEs resulting in variable defense repertoires across a bacterial species. This is also applicable to defense systems encoded in MGEs. Their defense systems can be under balancing selection because the hosts and MGEs they encounter vary in space and time.

Third, clones that are more abundant in a habitat are more susceptible to phages, because of their density [START_REF] Winter | Trade-offs between competition and defense specialists among unicellular planktonic organisms: the "killing the winner" hypothesis revisited[END_REF]. In this context, negative frequency-dependent selection may result in selection of rare alleles [START_REF] Brisson | Negative Frequency-Dependent Selection Is Frequently Confounding[END_REF], i.e., bacterial clones with defense systems that are rare in the population. As the population of individuals with the rare adaptive defense increases, antagonists with the ability to infect it also rise in frequency because they have more hosts available. This decreases the advantage of the initial clone and eventually cancels it when novel rare clones resistant to the MGEs emerge, thereby restarting the process of negative frequency-dependent selection. While negative frequency dependence in host-pathogen interactions has been extensively studied [START_REF] Woolhouse | Biological and biomedical implications of the co-evolution of pathogens and their hosts[END_REF], there is a paucity of data on its role in MGE-host interactions.

How is immunity gained?

What are the molecular mechanisms driving the variation of bacterial defenses? Some systems have dedicated molecular mechanisms for their own variation. For example, CRISPR/Cas systems drive their own diversification by the acquisition of spacers to target novel elements [START_REF] Hampton | The arms race between bacteria and their phage foes[END_REF]. Some R-M systems can also rapidly change their sequence specificity through recombination [START_REF] Dybvig | A family of phase-variable restriction enzymes with differing specificities generated by high-frequency gene arrangements[END_REF]. These mechanisms allow the host to fine-tune its defenses either directly to specific MGEs (CRISPR/Cas systems) or in more generic ways (variation in restriction sites).

Yet, the available evidence suggests that HGT and gene loss have major complementary roles in the diversification of defense repertoires at the species level. Accordingly, not only there is extensive evidence of the HGT of defense systems in MGEs [START_REF] Jeltsch | Horizontal gene transfer contributes to the wide distribution and evolution of type II restriction-modification systems[END_REF], but also their pseudogenes have been observed for many R-M [START_REF] Lin | Comparative genomics of the restriction-modification systems in Helicobacter pylori[END_REF] and CRISPR/Cas systems [START_REF] Stern | Self-targeting by CRISPR: gene regulation or autoimmunity?[END_REF]. The abundance of defense systems in MGEs suggests a very straightforward mechanism for the acquisitions of defense systems by the host: Systems are transferred across strains by the MGEs encoding them. Furthermore, MGEs are gained at high rates because of their infectiousness (explaining acquisition), and they are frequently lost from populations because of their cost (explaining loss). The rates of gain and loss of defense systems may thus be partly caused by the mobility and lability of the mobile elements encoding them.

Beyond explaining the acquisition of novel systems, the presence of defense systems in MGEs also offers some clues on how entirely novel defense strategies emerge. The recent discovery of many antiphage systems shows that they frequently consist in an assemblage of protein domains that are also present in proteins implicated in other cellular processes such as nucleases, kinases, deaminases, proteases, or ATPases [START_REF] Koonin | Evolutionary entanglement of mobile genetic elements and host defence systems: guns for hire[END_REF]. For instance, the Stk2 defense kinase is part of a family of kinases whose members are implicated in various cellular process such as the control of the cell cycle or the exit of dormancy [START_REF] Depardieu | A eukaryotic-like serine/ threonine kinase protects Staphylococci against phages[END_REF]. The antiphage viperins are close homologues to GTP cyclases involved in other functions [START_REF] Bernheim | Prokaryotic viperins produce diverse antiviral molecules[END_REF]. The co-option of proteins, or protein domains, with other functions, and the creation of novel assemblages leading to genetic innovation by recombination and mutation are likely facilitated by the horizontal transfer of defense systems across genetic backgrounds [START_REF] Touchon | The chromosomal accommodation and domestication of mobile genetic elements[END_REF]. While successful functional innovations by co-option of these systems may be unlikely, the very frequent transfer of systems and their rapid evolution may result in such a high rate of novel combinations of domains that some will eventually evolve to become novel defense systems. Such processes of co-option may have been at the independent origins of both Cas-9 and Cas-12 proteins from transposonencoded RNA-guided endonucleases [START_REF] Altae-Tran | The widespread IS200/ IS605 transposon family encodes diverse programmable RNA-guided endonucleases[END_REF][START_REF] Karvelis | Transposon-associated TnpB is a programmable RNA-guided DNA endonuclease[END_REF].

Novel defense systems, even if initially not part of MGEs, will eventually be captured by MGEs for their own use, with the consequence that they will be spread across microbial lineages. Transposases may play key roles in the process of translocating these systems from the chromosome to MGEs and vice versa. The subsequent transfer of defense systems to different genetic backgrounds is expected to favor the spread of defense systems that are robust to such changes. Accordingly, there is a broad distribution of most defense systems across the bacterial kingdom [START_REF] Tesson | Systematic and quantitative view of the antiviral arsenal of prokaryotes[END_REF]. It is also interesting to note the surprisingly broad activity of some defense systems recently described [START_REF] Doron | Systematic discovery of antiphage defense systems in the microbial pangenome[END_REF]. Cloning these genetic systems from distant species into E. coli and Bacillus subtilis yields defense phenotypes. The presence of defense systems on MGE that move across species might thus favor broad defense capabilities and mechanisms tolerant to changes in the genetic background.

Defending whom from what?

The rapid pace of discovery of novel defense systems has been facilitated by the use of assays where cells are challenged by virulent phages. As a result, the role of defense systems tends to be discussed in the light of phage-bacteria interactions. It does seem reasonable to assume that systems present in a microbial genome for a long time are protecting it from MGEs and especially against virulent phages given their lethality for the cell. Yet, systems encoded in MGEs are more likely to be selected because they benefit the MGE. In certain cases, a system increases the fitness of both MGE and host. For example, defense systems encoded in P4-like satellites were shown experimentally to protect the cell from several phages that the P4 element cannot exploit [START_REF] Rousset | Prophage-encoded hotspots of bacterial immune systems[END_REF]. In this case, the satellite and the cell have the same interest in preventing infection by phages that can kill the cell. In general, both MGEs and hosts will gain from preventing infection by virulent phages, explaining why MGEs defenses seem to target them frequently.

The interests of the MGE and the cell may not be so well aligned in other circumstances. In some cases, the advantage of the MGE defense system to the cell may be transient. Temperate phages that defend the cells from virulent phages are common [START_REF] Hussain | Rapid evolutionary turnover of mobile genetic elements drives bacterial resistance to phages[END_REF][START_REF] Dedrick | Prophagemediated defence against viral attack and viral counter-defence[END_REF][START_REF] Medvedeva | Virus-borne mini-CRISPR arrays are involved in interviral conflicts[END_REF] and provide a temporary relief to the host. But they may have little long-term impact in bacterial fitness if the victorious temperate phage is induced and lyses the cell. This is also exemplified by the exclusion systems encoded by conjugative systems or phages to fend off closely related elements [START_REF] Lu | Superinfection exclusion by T-even-type coliphages[END_REF][START_REF] Garcillan-Barcia | Why is entry exclusion an essential feature of conjugative plasmids?[END_REF]. Historically, these mechanisms have not been included in defense systems, but they are costly mechanisms that protect the cell from infection by MGEs, i.e., they fit the definition of defense systems as applied here to many other MGE genes. For example, the surface exclusion system of plasmid F prevents infection by similar plasmids thanks to the production of thousands of copies of an outer membrane protein that accounts for a large part of the plasmid carrier cost [START_REF] Achtman | Cell-cell interactions in conjugating Escherichia coli: role of traT protein in surface exclusion[END_REF]. A plasmid or a phage encoding an expensive exclusion/defense system against a similar element is engaging in an antagonistic interaction whose cost to the cell is large whereas the reward may be small because one such element is already in the cell (even if exclusion may protect cell integrity from too many simultaneous infections [START_REF] Garcillan-Barcia | Why is entry exclusion an essential feature of conjugative plasmids?[END_REF]). An even more extreme case concerns phages encoding defense or antidefense systems against their satellites. These are engaging in an interaction with their parasites in a way that resembles their own interaction with the cell (but with their own position reversed as they are now the ones being exploited) [START_REF] Fillol-Salom | Beyond the CRISPR-Cas safeguard: PICI-encoded innate immune systems protect bacteria from bacteriophage predation[END_REF]. Such phage-encoded defense systems could be highly deleterious to the cell because they remove a protective satellite and favor a phage that will eventually kill the host.

The misalignment of interests between MGEs and the host is particularly striking when it concerns abortive infection systems, because these are extremely costly to the cell [START_REF] Lopatina | Abortive infection: bacterial suicide as an antiviral immune strategy[END_REF]. The traditional view is that such strategies can only be selected in very particular cases favoring cooperation between individuals, e.g., in structured environments where the death of a cell benefits its neighboring kin [START_REF] Nadell | Emergence of Spatial Structure in Cell Groups and the Evolution of Cooperation[END_REF]. A recent investigation of abortive infection provided by retron elements suggests that retron-encoding bacteria lose in competition with bacteria lacking the retron when challenged by a phage even in a structured environment [START_REF] Berryhill | An evolutionary perspective of suicide as a way to protect bacteria from being killed by phage[END_REF]. Yet, genomic data suggest that abortive infection systems are very frequent [START_REF] Tesson | Systematic and quantitative view of the antiviral arsenal of prokaryotes[END_REF], which requires an explanation. The presence of abortive infection systems on MGEs could facilitate the control of epidemics of competitive elements and would justify their abundance in the host. Such systems could be deleterious to the host if they drive cell death upon infection by elements with little negative impact on its fitness. But in other circumstances, the presence of these systems in MGEs could benefit the host by enforcing cooperation [START_REF] Rankin | What traits are carried on mobile genetic elements, and why?[END_REF], since the transfer of the MGEs to sensitive hosts spreads the abortive system and therefore favors the cooperative process.

To understand the fitness impact of defense systems, it is thus important to know if they are encoded in MGEs. The identification of functional MGEs is difficult both computationally and experimentally, since many MGEs are poorly known and many of the others are defective [START_REF] Touchon | The chromosomal accommodation and domestication of mobile genetic elements[END_REF]. It is often even more difficult to predict which genetic elements are being targeted by the defense system. That many systems are effective against virulent phages may be in part the result of ascertainment biases, since virulent phages are often used to identify defense systems. One might also argue that virulent phages are going to be targeted by hosts and most MGEs because they kill the host and its MGEs. However, many systems, among which all those using epigenetic markers like R-M, target generic exogenous DNA independently of it being part of a phage genome. This makes it particularly hard to know who they were selected to target.

CRISPR/Cas systems are unique among defense systems because they keep a record of the elements against which they defend and therefore allow to pinpoint the elements that have been sufficiently deleterious to result in selection of the corresponding CRISPR spacers. The analysis of the spacer content can thus inform on the selection pressure that maintain CRISPR immunity. While some CRISPR/Cas systems predominantly carry spacers targeting bacteriophages, others like type IV CRISPR/Cas systems predominantly carry spacers against plasmids [START_REF] Pinilla-Redondo | Type IV CRISPR-Cas systems are highly diverse and involved in competition between plasmids[END_REF], and many carry both [START_REF] Marraffini | CRISPR interference limits horizontal gene transfer in staphylococci by targeting DNA[END_REF]. These results suggest that systems encoded in MGEs may be targeting other competing MGE that are not costly to the cell. They may even be targeting elements that are adaptive to the cell or targeting the cell itself (e.g., addictive systems or antidefense systems), thereby lowering bacterial fitness. Knowing which genetic elements are being targeted in nature will require a better mechanistic understanding of the defense systems and the ecological contexts where they are selected for.

How do defense systems affect gene flow?

Acquisition of defense systems requires HGT, but defense systems are expected to decrease the rates of transfer of MGEs, and thus decrease HGT. Gene flow, including allelic recombination and acquisition of novel genes by HGT, is a key driver of bacterial evolution, and there is an evolutionary cost to restricting it. For example, epidemic Vibrio cholerae strains depend on a prophage for a key virulence factor (the cholera toxin). When they are infected by SXT-like conjugative elements carrying defense systems, they are hampered in their ability to acquire the toxin [START_REF] Legault | Temporal shifts in antibiotic resistance elements govern virus-pathogen conflicts[END_REF]. More generally, a computational analysis of approximately 80 species showed that gene flow is decreased between strains with incompatible R-M systems [START_REF] Oliveira | Regulation of genetic flux between bacteria by restriction-modification systems[END_REF]. When R-M systems diversify within populations, because of bacterial/MGE antagonistic coevolution, DNA exchanges become more frequent between strains with similar systems (Fig 3). As a result, defense systems have the potential to fragment gene flow within bacterial populations.

The presence of mechanisms of defense may impact gene flow in diverse ways. One would expect that very generic systems, like R-M, would have an important effect on restricting gene flow, whereas more targeted systems, like CRISPR/Cas, would tend to affect gene flow driven by a few particularly deleterious elements. Accordingly, the impact of CRISPR/Cas in restricting gene flow has remained controversial [START_REF] Gophna | No evidence of inhibition of horizontal gene transfer by CRISPR-Cas on evolutionary timescales[END_REF][START_REF] Wheatley | CRISPR-Cas systems restrict horizontal gene transfer in Pseudomonas aeruginosa[END_REF].

The negative impact of defense systems on gene flow has been regarded as a costly by-product of selection for protection of the cell. But MGE defense systems may be selected exactly because they block HGT to prevent the cell from acquiring competitor MGEs. The resulting sexual barriers are advantageous for the MGE but can be deleterious to the cell. Yet, these barriers are not unbreakable. The presence of multiple MGEs in genomes is in itself an indication of this. Accordingly, R-M systems only provide transient protection from phages [START_REF] Korona | Phage-mediated selection for restriction-modification[END_REF], because one single successful infection is enough to result in correctly methylated phages that can pass the restriction barrier and then propagate across the population. Further work is needed to quantify the impact of different defense systems in gene flow, to identify the types of MGEs that are most affected, and to understand how defenses affect host evolvability.

The effect of defense systems on gene flow is not always negative. Transduction, the transfer of bacterial DNA in viral particles, is favored by the existence of CRISPR/Cas systems in recipient cells when they target the phage DNA (Fig 1). This is because the CRISPR/Cas system targets the phage DNA, protecting the cell, but not the bacterial DNA coming within viral particles, resulting in cells that receive exogenous cellular DNA while being protected from phages [START_REF] Watson | CRISPR-Cas-Mediated Phage Resistance Enhances Horizontal Gene Transfer by Transduction[END_REF]. In this case, the defense system facilitates gene flow. Is it defense, counter-defense, addiction, or something else? While many systems have been called defensive relative to their ability to defend bacteria or MGEs from other MGEs, they may be addictive or attack systems when part of MGEs. A striking example is provided by phage-satellite interactions. The reproduction of virulent phages of the ICP1 family in V. cholerae is abolished by phage-inducible chromosomal island-like elements (PLEs) [START_REF] Seed | A bacteriophage encodes its own CRISPR/Cas adaptive response to evade host innate immunity[END_REF]. In response, ICP1 phages have evolved the ability to encode a CRISPR/Cas system or specific nucleases that eliminate the satellite [START_REF] Barth | A chimeric nuclease substitutes a phage CRISPR-Cas system to provide sequence-specific immunity against subviral parasites[END_REF]. In this context, they could be regarded as attack systems from the point of view of the bacterium, because their success results in cell death. They could also be regarded as phage counter-defenses, if satellites are considered as a bacterial defense system. There is thus some ambiguity between functions of defense, counter-defense, and attack, depending on the perspective of the observer. Some systems may have multiple roles specifically when encoded in MGEs. R-M systems contribute to the stabilization of plasmids in the cell by acting as poison-antidote addictive systems [START_REF] Naito | Selfish behavior of restriction-modification systems[END_REF]. In such cases, loss of the plasmid and its R-M system prevents further expression of the latter. Since endonucleases have longer half-lives than methylases, this eventually results in genomes that are restricted because they are insufficiently methylated. R-Ms are thus part of the attack arsenal of plasmids. Yet, these R-M systems can also protect the consortium (cell and plasmid) from infection by other MGEs, thereby acting as cell defense systems. Plasmids also frequently encode toxin-antitoxin systems that behave as addiction systems [START_REF] Dy | A widespread bacteriophage abortive infection system functions through a Type IV toxin-antitoxin mechanism[END_REF], some of which are implicated in phage defense. Homologues of cell defense systems encoded in MGEs can thus be addiction tools with positive side effects in cellular defense. It is possible that such systems have started as genetic elements that propagate selfishly in genomes because of their addictive properties and have later been co-opted to become defense systems (although the inverse scenario cannot be excluded at this stage).

Are MGEs at the origin of "defense islands"?

It was observed a decade ago that defense systems are often clustered in a few loci in microbial chromosomes [START_REF] Makarova | Defense islands in bacterial and archaeal genomes and prediction of novel defense systems[END_REF]. This characteristic was leveraged into a systematic method to discover novel systems by colocalization with known ones [START_REF] Doron | Systematic discovery of antiphage defense systems in the microbial pangenome[END_REF]. Interestingly, recent data have revealed that antidefense systems, both anti-R-M and anti-CRISPR/Cas, also tend to cluster in bacterial genomes, often in recognizable MGEs [START_REF] Pinilla-Redondo | Discovery of multiple anti-CRISPRs highlights anti-defense gene clustering in mobile genetic elements[END_REF]. The clustering of these systems could result from selection for the coregulation of their expression, but there is very little evidence of that.

The presence of defense systems in MGEs provides a simple explanation for the colocalization of defense and counter-defense systems in a few locations of the bacterial chromosome (Fig 4). Genes acquired by HGT, and MGEs in particular, tend to integrate at a small number of chromosome hotspots [START_REF] Touchon | Organised genome dynamics in the Escherichia coli species results in highly diverse adaptive paths[END_REF][START_REF] Rodriguez-Valera | Explaining microbial population genomics through phage predation[END_REF][START_REF] Oliveira | The chromosomal organization of horizontal gene transfer in bacteria[END_REF][START_REF] Hackl | Novel integrative elements and genomic plasticity in ocean ecosystems[END_REF], and some of these were found to have defense systems over a decade ago [START_REF] Avrani | Genomic island variability facilitates Prochlorococcus-virus coexistence[END_REF]. These MGEs may degenerate by the accumulation of mutations, deletions, and insertions. Chromosome hotspots are thus littered with remnants of previous events of transfer. As MGEs are integrated and eventually degrade in the hotspot, some genes may remain functional because they are adaptive for the cell [START_REF] Touchon | The chromosomal accommodation and domestication of mobile genetic elements[END_REF]. Since MGEs often carry defense and antidefense systems, their rapid turnover in hotspots may be accompanied by selection for the conservation of some of their defense systems. Ultimately, this could result in their cooption by the host cell. As rounds of MGE integration/degradation succeed in natural history, the remnant co-opted defense systems form clusters in the chromosome, i.e., they form defense islands. Since studies on defense islands have not focused on separating those in MGEs from the others, it remains unclear whether defense islands might simply be an assemblage of functional MGEs or whether integration/degradation events play a significant role in stabilizing clusters of defense systems.

The clustering of defense systems may facilitate the evolution of functional interactions between them or the coregulation of their expression. For example, it has been observed that type I and type III CRISPR/Cas systems provide 2 integrated levels of defense against phages [START_REF] Silas | Type III CRISPR-Cas systems can provide redundancy to counteract viral escape from type I systems[END_REF]. These systems are often colocalized [START_REF] Bernheim | Atypical organizations and epistatic interactions of CRISPRs and cas clusters in genomes and their mobile genetic elements[END_REF]. Even if advantages of their colocalization in the genome are yet unclear, it may facilitate cotranscription or coevolution of the systems. The clustering of these systems in islands could also facilitate their subsequent transfer as a block by HGT to other cells. This could occur by mechanisms able to transfer large genetic loci such as conjugation starting a conjugative element integrated in the chromosome or lateral transduction starting from a neighboring phage [START_REF] Fillol-Salom | Beyond the CRISPR-Cas safeguard: PICI-encoded innate immune systems protect bacteria from bacteriophage predation[END_REF].

Outlook

MGEs of bacteria and archaea encode accessory functions of adaptive value for the host. That many of these accessory functions concern systems facilitating host infection or MGE protection from other elements testifies to the importance of such interactions for the fitness of MGEs. These defense systems may also be adaptive to the host, but this should not be taken for granted. Having this conceptual framework in mind can aid the field move forward along the following lines.

-Identify novel defense systems. Many defense systems are poorly known and probably many more remain to be uncovered. The recent expansion in the number and type of defense systems occurred because researchers searched for novel systems colocalizing with previously known ones. Many novel systems may be awaiting discovery among the countless MGEs present across microbial genomes. Since these genes are often found at specific locations in MGEs, e.g., near the cos site of P4-like satellites [START_REF] Rousset | Prophage-encoded hotspots of bacterial immune systems[END_REF], these locations may be treasure troves of novel defense systems.

-Understand the mechanisms of defense. Most of the studies on the mechanisms of defense systems use virulent phages as targets. Yet, systems encoded by MGEs may target different elements and having this information may result in the discovery of novel molecular mechanisms, especially among systems targeting specific MGE functions. Recent works have -Identify counter-defense mechanisms. Counter-defense mechanisms are now being identified for the best-known mechanisms of defense. Integrating the knowledge of the existence of mechanism of defense in an element, its molecular mechanism, and the elements being targeted could provide important clues on where to find novel antidefense systems from known or novel defense systems.

-Inference of the networks of defenses. As defense systems provide multiple layers of defense against MGEs, it is important to understand what these layers are and how they interact. Ultimately, immune systems of bacteria might rely on complex networks of functional and genetic interactions between defense systems that provide a robust and thorough response to most parasites. These networks may resemble those of the eukaryotic immune system. The parallel between innate (R-M) and adaptive (CRISPR/Cas) immune systems has been drawn before [101], and some defense systems have homologues in eukaryotes and bacteria [START_REF] Bernheim | Prokaryotic viperins produce diverse antiviral molecules[END_REF].

-Identification of the mechanisms generating novel defense systems. These evolutionary mechanisms may also share similarities across the tree of life, since some regulatory elements or components of the immune system of vertebrates and plants also derive from co-options of MGEs [102,103]. Balancing selection seems to explain the evolutionary patterns of defense systems in bacteria, plants and animals [START_REF] Fijarczyk | Detecting balancing selection in genomes: limits and prospects[END_REF]. Yet, one must keep in mind that a lot of the variation in the bacterial immune response is associated with rapid gain and loss of defense systems, many of which in MGEs, which is different from the processes driving the diversification of immune systems of vertebrates.

-Mapping the interactions between MGEs and the host. Knowing the mechanisms of defense systems carried by a specific MGE can hint at their possible targets and therefore reveal the MGEs (or host) affected by the element. This can be leveraged to map antagonistic interactions between MGEs. There are already several examples of this for CRISPR/Cas systems in MGEs, where the analyses of the spacers in the CRISPR array allowed the identification of the MGEs being targeted by the system [START_REF] Seed | A bacteriophage encodes its own CRISPR/Cas adaptive response to evade host innate immunity[END_REF][START_REF] Pinilla-Redondo | Type IV CRISPR-Cas systems are highly diverse and involved in competition between plasmids[END_REF]104].

-Fighting pathogenic bacteria. Virulence factors and antimicrobial resistance genes are frequently carried by MGEs. A better understanding of the defense, addiction, or attack systems that these elements employ to ensure their propagation might lead to the identification of novel strategies to counteract the spread of these costly elements, for instance, by favoring competing harmless MGEs. The presence of antiphage systems on MGEs could also promote the rapid evolution of resistance to phage therapies, and conversely, the identification of counter-defenses deployed by phages and other MGEs might provide solutions for the selection or engineering of more potent therapeutic phages.

Above all, to understand the roles of defense and/or counter-defense systems, given their abundance in MGEs, one must attain a better understanding of the complex networks of interactions between these semiautonomous agents and the host. Their study will shed novel light on the function, evolution, and ecology of microbes.

Fig 1 .

 1 Fig 1. Examples of defense systems discussed in the text. Homologous recombination via the RecBCD pathway can defend from MGEs because RecBCD is a powerful exonuclease that degrades linear double-stranded DNA (but is inactivated by some phage encoded proteins, like Gam). Epigenetic modifications are the basis of many defense systems that can be counteracted by phage proteins, like Ocr in phage T7, or by epigenetic modification of phage DNA. Abortive infection is a costly defense strategy that induces cell growth arrest or death when a threat to the cell is detected. Adaptive immunity by CRISPR/Cas systems targets MGEs with specific DNA sequences, while allowing other exogenous DNA to remain in the cell and eventually recombine with the chromosome. CRISPR/Cas, clustered regularly interspaced short palindromic repeats/CRISPR associated protein; MGE, mobile genetic element. https://doi.org/10.1371/journal.pbio.3001514.g001

Fig 2 .

 2 Fig 2.Defense and antidefense systems are often studied in the context of the interaction between one host and one MGE, usually a virulent phage (left). Yet, the presence of numerous MGEs in populations and their ability to encode their own defense systems renders the picture more complex (right). Virulent phages establish antagonistic interactions with the other MGEs and the cell[START_REF] Taylor | The diverse impacts of phage morons on bacterial fitness and virulence[END_REF]. But the associations between the other MGEs and the cell can be more diverse (2 to 7). Temperate phages and conjugative plasmids exploit their cellular host (2 and 4) and can be exploited by other MGEs (3 and 5). Plasmids often encode systems that are effective barriers to phages, e.g., R-M[START_REF] Toro | Plasmid diversity and adaptation analyzed by massive sequencing of Escherichia coli plasmids[END_REF]. Phages are a threat to plasmids when they kill the host cell[START_REF] Toro | Plasmid diversity and adaptation analyzed by massive sequencing of Escherichia coli plasmids[END_REF]. Satellites may benefit the host by diminishing phage infection[START_REF] Bobay | Pervasive domestication of defective prophages by bacteria[END_REF]. Most of these interactions (2 to 8) can at times be beneficial to both partners, e.g., when a conjugative plasmid provides a nosocomial bacterium with antibiotic resistance. MGE, mobile genetic element.

Fig 3 .

 3 Fig 3. Diversification of R-M systems changes gene flow within species.When a population has a single R-M system (left), HGT between cells is not affected by restriction. As the diversity of systems increases (phylogenetic tree at the center), the subpopulations of individuals with similar R-M systems exchange genes at higher rates (high flow) than those with different R-M systems (low gene flow, right top), leading to fragmentation of gene flow in populations (right bottom). HGT, horizontal gene transfer; R-M, restriction-modification. https://doi.org/10.1371/journal.pbio.3001514.g003

Fig 4 .

 4 Fig 4. MGE turnover at hotspots may result in defense islands. MGEs tend to integrate the chromosome at a few hotspots and may subsequently be inactivated by mutations resulting in the loss of genes that are not adaptive to the host. The succession of integration/partial deletion of MGEs if accompanied by the co-option of the defense systems may result in clusters (or islands) of defense systems in hotspots. MGE, mobile genetic element. https://doi.org/10.1371/journal.pbio.3001514.g004

PLOS Biology | https://doi.org/10.1371/journal.pbio.3001514January 13, 2022

Acknowledgments

The authors thank Aude Bernheim, Fre ´de ´rique Le Roux, and Maria Pilar Garcillan Barcia for comments and suggestions and Marie Touchon for discussions and graphical elements for the figures.

This study was funded by Agence Nationale de la Recherche (IBEID ANR-10-LABX-62-IBEID) (EPCR); Equipe Fondation pour la Recherche Me ´dicale (EQU201903007835) (EPCR) and Agence Nationale de la Recherche (SALMOPROPHAGE, ANR-16-CE16-0029) (EPCR). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.


Fabrice Boudot

Pierrick Gaudry

Aurore Guillevic

Nadia Heninger

Emmanuel Thomé

Paul Zimmermann

The state of the art in integer factoring and breaking public key cryptography

The security of essentially all public-key cryptography currently in common use today is based on the presumed computational hardness of three number-theoretic problems: integer factoring (required for the security of RSA encryption and digital signatures), discrete logarithms in finite fields (required for Diffie-Hellman key exchange and the DSA digital signature algorithm), and discrete logarithms over elliptic curves (required for elliptic curve Diffie-Hellman and ECDSA, Ed25519, and other elliptic curve digital signature algorithms).

In this column, we will review the current state of the art of cryptanalysis for these problems using classical (non-quantum) computers, including in particular our most recent computational records for integer factoring and prime field discrete logarithms.

Integer Factoring and RSA

Integer factorization is probably the most well known of the computational problems we discuss in this article.

The RSA cryptosystem is "based on" the hardness of integer factoring in that if an adversary can factor the public modulus N contained in an RSA public key into its prime factors p and q, they can easily compute the private key. Interestingly, although factoring the public modulus N appears to be the best approach to break RSA, these problems are not known to be equivalent: there might be an algorithm to efficiently decrypt RSA ciphertexts or forge digital signatures that does not require or reveal the factorization of the modulus.

Factoring small numbers via trial division is easy: decomposing 91 into 7 times 13, or 2701 into 37 times 73. Even finding factors of large numbers may also be easy: one can see that the integer 26674 is divisible by 2. But an algorithm that can efficiently factor any integer with hundreds of decimal digits is still not known.

The integer factorization problem is easy to state, and mathematicians had already developed factorization algorithms that ran much faster than brute force before the 1970s, when the problem of factorization became a cornerstone of public-key cryptography. There is a wide variety of classical algorithms that can factor integers of various forms: Pollard's rho algorithm can find a factor p of an integer in time O( √ p), Pollard's p -1 algorithm can efficiently find a factor p of an integer if the value p -1 has only "small" prime factors, Fermat factorization can efficiently factor an integer N = a 2 -b 2 if a and b are "close" to √ N , and so on. The construction of the RSA modulus N is designed to evade these "special-purpose" factoring algorithms. This leaves the cryptanalyst no choice but to use a so-called "general purpose" factoring algorithm, which we will consider next.

Currently, the most efficient algorithm to factor RSA moduli is called the General Number Field Sieve (GNFS, or sometimes just NFS). GNFS is described in [START_REF]The development of the number field sieve[END_REF], but its ancestry can be traced to a few years earlier as a means to factor integers of a particularly suitable form [START_REF]The development of the number field sieve[END_REF][START_REF] Lenstra | The number field sieve (extended abstract)[END_REF].

Sketch of the NFS algorithm

Let N = pq be a composite number. We will illustrate the algorithm by factoring the toy example N = 2701. Observe that modulo N , a number has up to four square roots; for example (±119) 2 = (±1287) 2 = 656 mod N . A suitable pair of these square roots can be used to factor N : we have 119 2 -1287 2 = (119+1287)(119-1287) = 0 mod N . If we are lucky, the factors of this difference of squares split the factors of N , and we can use the GCD algorithm to find these factors. In our example, we have gcd(119 + 1287, N ) = 37 and gcd(119 -1287, N ) = 73. If we got unlucky, we can simply look for more congruences of the form X 2 = Y 2 mod N until we find one such that X ̸ = ±Y mod N .

This basic idea dates back to Fermat factorization, but a linear search for congruences of squares does not lead to an efficient factoring algorithm. To improve the running time, one can instead construct squares as products of congruences of known factorization modulo N .

This results in a two-stage algorithm. First, in the relation collection step, one collects many multiplicative relations modulo N . The desired relations are smooth, meaning that each side factors completely into relatively small primes. Next, to construct a relation of squares, the algorithm observes that a square integer has even exponents in its prime factorization, and thus once enough relations have been collected, one can do linear algebra over the vector of exponents modulo 2 to solve the system and obtain a congruence of squares. Returning to our toy example N = 2701, one has 52 2 = 3 mod N and 53 2 = 2 2 • 3 3 mod N , so that (52 • 53) 2 = 55 2 = 18 2 mod N , and gcd(55 + 18, N ) = 73.

The Quadratic Sieve and CFRAC (Continued FRACtion method) factoring algorithms follow the general approach outlined above. The expected running time of these algorithms depends on optimizing the chosen smoothness bound for desired relations. A lower smoothness bound means that the algorithm does less work to test a candidate relation, and less work in the linear algebra phase, but one must iterate through more candidate relations in order to find suitably smooth relations.

The Number Field Sieve also uses the above approach, but it takes advantage of more advanced number theory. In particular, by constructing integer relations by factoring elements in a number field, this reduces the size of the integer relations to be tested for smoothness, thus increasing the probability that a candidate relation is smooth, and resulting in less work to find the desired number of relations. Decreasing the size of the integers to be tested makes a dramatic difference overall: as a concrete example, 0.5% of 32-bit integers are 8-bit smooth, but only 0.0025% of 48-bit integers are.

This results in an algorithm divided into five stages: polynomial selection, in which one chooses a number field to work in, followed by relation collection, a filtering stage in which one reduces the size of the next phase, linear algebra, and a final phase called the square root phase in the factoring context (see Figure 1). The relation collection and linear algebra phases, which are described in general terms above, occupy the bulk of the running time.

Asymptotic running time

The running time of GNFS is not easy to express. Heuristically, it is possible to derive an asymptotic formula from coarse asymptotic estimates of the number of smooth integers. The cost of factoring N with GNFS, as N grows, is exp (64/9

) 1/3 (log N ) 1/3 (log log N ) 2/3 (1 + o(1)) .
This running time is subexponential, meaning that it is faster than a purely exponential-time algorithm in log N would be, but slower than a polynomial-time algorithm. However, the 1 + o(1) factor hides a significant amount of performance for concrete parameters. An algorithmic improvement can bring a polynomial speedup to the algorithm (that is, a polynomial in log N ), without leaving this broad complexity class. While this general asymptotic running time for the number field sieve has not been improved since the algorithm was developed in the early 1990s, there has been algorithmic progress that has had a dramatic impact on the actual running time of the algorithm, all of which is hidden by the "o(1)" term.

The recommended key sizes for RSA in practice are selected based on this asymptotic estimate of running time. This subexponential running time of the NFS algorithm is why RSA key sizes are so much larger than symmetric key sizes at the same security level. The best attacks against the AES cipher take only slightly less than 2 128 time for a 128-bit key, so 128-bit AES is expected to provide nearly 128 bits of security. However, for RSA, the usual estimate is that in order to have 128 bits of security, one should use at least a 3072-bit modulus.

Practical progress

Although the general structure of the number field sieve algorithm has remained roughly the same for 30 years, there have been many refinements during that time that have improved performance by significant constant factors. At a high level, the number field sieve is a complex algorithm with a large number of adjustable parameters that affect algorithm stages in different and not always well understood ways.

Below, we touch on a handful of recent refinements to the most time-consuming steps of NFS: polynomial selection, relation collection, and linear algebra.

In the polynomial selection step, an implementation uses analytic estimates and experimental sampling to find a good choice of number field. The properties of the chosen polynomial have a significant effect on the overall running time of the algorithm, so it can be worthwhile to expend effort on this step. Our recent 795-bit and 829-bit factoring records took advantage of improvements to polynomial selection to achieve relatively faster running times than extrapolations from previous records would suggest [START_REF] Boudot | Comparing the difficulty of factorization and discrete logarithm: A 240-digit experiment[END_REF]. Yet there is reason to expect that further progress is possible: if "ideal" polynomials in the sense of [START_REF] Kleinjung | Polynomial Selection for the Number Field Sieve[END_REF] could be found, relation collection could be made almost twice as fast. An efficient method of finding such "ideal" polynomials remains an open problem.

The relation collection step is generally the computationally most expensive part of the NFS algorithm. Fortunately, it is embarrassingly parallel, and recent computations have been able to make extensive use of idle time on large clusters. There are a variety of algorithms that can be applied to this problem, which can vary in speed and memory requirements. The recent factoring records spent a good deal of effort in exploring the relative benefits of many of these algorithms, some of which had never been used before. The choice and parameterization of algorithms in relation collection also interacts with the NFS algorithm in general (with linear algebra, for example), which necessitates some fine-tuning. In our latest record computations, this fine-tuning work was supported by extensive use of simulations to estimate the running time of each stage of NFS and optimize the complex interactions between parameters, which proved tremendously useful.

Historically, the linear algebra phase was believed to be a major barrier to scaling factoring to cryptographically relevant numbers because of prohibitively large memory requirements. It was also believed that this phase could not effectively be parallelized, and thus it would be a bottleneck. Research progress has shown that both of these statements are false. The block Wiedemann algorithm, which is used for NFS sparse linear algebra, has evolved both algorithmically and in practice into a very versatile tool. It can effectively be parallelized, and recent record computations parallelized this phase across multiple remote computational resources. And on modern computing systems, the memory requirements do not seem to be limiting the scale of current computations at all.

All of these refinements are specific to the number field sieve algorithm. A brand new algorithm might yet be discovered in the future, which could completely change the integer factoring landscape.

The state of the art

By convention, factoring records are often measured using the RSA challenges published by RSA Labs in 1991, although the cash prizes expired years ago.

The latest factoring (and discrete logarithm) records are depicted in Figure 2, culminating with the factorization of RSA-250 (a 829-bit composite number) in February 2020, for a computation cost of about 2,700 core-years.

These academic results are far from the limit of feasibility, especially for a state-level attacker. It is obvious that larger computations are possible, and it is widely accepted that 1024-bit factoring and discrete logarithm The Number Field Sieve algorithm for factoring is a complex multi-stage algorithm in which each stage has different computing requirements and potential for parallelization, as well as numerous tuneable parameters that enable different tradeoffs. The number field sieve algorithm for discrete logarithm is closely related to the NFS algorithm for factoring. are feasible now, with hardware and software that currently exist. A ballpark estimate is that factoring a 1024-bit key would be about 200 times harder than RSA-250, or around 500,000 core-years of computation.

The associated sparse matrix is expected to have about 4 billion rows and columns. Dealing with such a matrix would mobilize tens of thousands of CPU cores over several months, which is certainly feasible. The challenge of computing discrete logarithms for this size is a step further in terms of difficulty and resource requirements, but would still be feasible. Nobody has done such a computation yet in public, since academic research teams don't have access to that much computing power. From an academic standpoint, carrying out such a computation would not surprise the research community. However, carrying out these types of concrete cryptanalytic computations appears to be necessary to encourage users to move to stronger key sizes and algorithms in the real world. Recent history has shown that in the context of hash functions, work on rogue MD5 certificates [START_REF] Stevens | Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate[END_REF] or the computation of actual collisions on SHA-1 [START_REF] Stevens | The first collision for full SHA-1[END_REF] were both instrumental in the deprecation of these insecure hash functions.

2 Finite field discrete logarithms and Diffie-Hellman

In the discrete logarithm problem over prime fields, g and p are public integers, and the problem is, given some input y = g x mod p, to find the discrete logarithm x.

More generally, we can consider the discrete logarithm problem over finite fields GF(p n ) of p n elements, where p is a prime (the characteristic) and n is an integer (the extension degree). Mathematically, there are three general algorithmic classes: the prime field case GF(p) where n = 1, the small-characteristic case where p is very small (typically p = 2 or p = 3), and the medium characteristic, which lies between these two extremes.

The security of Diffie-Hellman key exchange is "based on" the discrete logarithm problem in the sense that if an attacker can compute the discrete logarithm of one of the publicly transmitted key exchange values, they can use this value to easily compute the shared secret. However, like the relationship between factoring and RSA, it is not known whether the two problems are equivalent: although discrete logarithm is the best attack known to solve the Diffie-Hellman problem, there may be some yet-undiscovered algorithm to compute the shared secret that does not reveal the discrete logarithm of the public values.

The discrete logarithm problem seems to be closely related to the problem of integer factoring, and a number of algorithms for solving integer factorization have analogues to solve the discrete logarithm problem.

Strangely, this eerie connection between the two problems does not seem to have been formally understood.

Discrete logarithms in prime fields

The most common case of discrete logarithm-based cryptography takes place when the public modulus p is a prime, and g is a generator of a prime-order multiplicative subgroup modulo p. As in the case of RSA, the prime structure and size of these parameters are chosen to avoid a number of elementary discrete logarithm algorithms that work for small, composite-order, or otherwise structured groups like the Pollard rho algorithm, parallel collision search, and Pohlig-Hellman algorithm.

Once these elementary algorithmic attacks have been thwarted by proper parameter choices, the best algorithm in general to solve the discrete logarithm problem is the number field sieve algorithm for discrete logarithms, or NFS-DL for short. Its complexity depends on the modulus p. The asymptotic running time for NFS to factor an integer N is the same as the asymptotic running time for NFS-DL for a modulus p of the same size as N .

The NFS-DL algorithm, like the NFS algorithm for factoring, has five main stages: polynomial selection, sieving, filtering, linear algebra, and finally the computation of individual logarithms (see Figure 1).

The first three stages have a similar structure to the analogous algorithm for factoring, but there are some important differences. In the polynomial selection phase, the fact that the general setup of NFS-DL targets a field instead of a ring permits an improved strategy that yields much better results for current record computational sizes: in our most recent record, this allowed a 5-fold speedup [START_REF] Boudot | Comparing the difficulty of factorization and discrete logarithm: A 240-digit experiment[END_REF].

Second, the linear system to be solved is no longer modulo 2, but instead modulo a larger prime, in particular the order of the subgroup generated by g. This makes linear algebra more expensive than in the factoring case. The final difference is that polynomial selection, relation collection, and linear algebra depend only on the prime modulus p, and not on the target value to compute the discrete logarithm of. This is different from the case of factoring, where all stages of the NFS algorithm depend on the integer N to be factored, and means that an attacker could carry out the most expensive parts of a discrete logarithm computation offline, and reuse them for many different key exchanges using the same parameters [START_REF] Adrian | Imperfect forward secrecy: How Diffie-Hellman fails in practice[END_REF].

Current records and comparison with factoring

The current record for largest discrete logarithm computation in a prime field was done modulo a 795-bit prime [START_REF] Boudot | Comparing the difficulty of factorization and discrete logarithm: A 240-digit experiment[END_REF]. This computation took 3,100 core-years and little over 1 calendar year of computational time.

While the asymptotic running time of the NFS algorithm is the same for discrete logarithm and factoring, discrete logarithm has generally been perceived as somewhat more difficult, mainly because of the increased cost for the linear algebra phase. This can be seen empirically in Figure 2, as discrete logarithm records have historically lagged several years behind the size of record factorizations. However, recent computations have shown that the improved flexibility in polynomial selection can result in much closer practical running times: for 795-bit factoring and discrete logarithms, [START_REF] Boudot | Comparing the difficulty of factorization and discrete logarithm: A 240-digit experiment[END_REF] shows that computing discrete logarithms is about three times harder than factoring.

The small characteristic case

One can also consider the problem of computing discrete logarithms in finite fields of order 2 n and 3 n , or more generally p n for small p. It has a close relationship to the discrete logarithm problem in "large-characteristic" fields of order p described above. For more than two decades, the best algorithm to solve discrete logarithm in the small-characteristic case was the function field sieve, an algorithm closely related to the number field sieve, and the best estimates of its asymptotic running time were similar to those for large-characteristic discrete logarithms using the number field sieve.

However, starting in 2013, a series of algorithmic advances led to dramatic improvements in running time for the small characteristic case, culminating in new algorithms of quasi-polynomial (n O(log n) ) running-time [START_REF] Barbulescu | A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF]. (Remarkably, this line of research has recently led to a proven algorithm [START_REF] Kleinjung | Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic[END_REF] achieving quasi-polynomial complexity, a unique feat among algorithms for factoring and discrete logarithms in finite fields.) The immediate consequence of this breakthrough was that the discrete logarithm problem in fields of the form GF(2 n ) was no longer hard enough for cryptography. While these fields had rarely been considered for cryptographic use, their demise also discarded other cryptographic constructions that implicitly relied on their hardness, such as supersingular elliptic curves over binary fields, which used to be part of the zoo of curves potentially useful in pairing-based cryptography.

The specific advances used to achieve these results do not seem to apply to the large-characteristic case. At the same time, as in the case of RSA, parameter sizes for discrete logarithm-based cryptography including Diffie-Hellman key exchange, DSA digital signatures, and ElGamal encryption are set based on extrapolations of the running time of NFS-DL for large-characteristic fields. The main evidence for the security of these parameter choices is the lack of asymptotic improvements in the large characteristic case during the last three decades. However, as the significant improvement in the small-characteristic case shows, previously overlooked improvements can be found after decades of stasis.

Discrete logarithms in small to moderate degree extension fields

Between the "easy case" of fields of extremely small characteristic and the more challenging case of prime fields detailed above, the discrete logarithm problem in extension fields is also an interesting research area. This topic is of particular interest to pairing-based cryptography, which implicitly relies on the hardness of the DLP in moderate-degree extensions of prime fields. In turn, this problem also matters for some cryptocurrency applications that use succinct and efficient zero-knowledge proofs built from elliptic curve pairings.

Special variants of NFS are well adapted in this case, notably the "Tower" Number Field Sieve (TNFS). Several new algorithms have emerged in recent years, and practical progress has been steady. The current record is a 521-bit computation in a degree-6 field [START_REF] De Micheli | Lattice enumeration for Tower NFS: a 521-bit discrete logarithm computation[END_REF]. As a result of this ongoing progress, accurate assessments of feasibility limits for the DLP in such fields are much harder to obtain, as they rely on fragile and fast-changing empirical evidence.

Elliptic curve discrete logarithms

The discrete logarithm problem on elliptic curve (ECDLP) has seen considerably less cryptanalytic progress than factoring or finite-field discrete logarithms. The case of highest cryptographic interest (for elliptic curve Diffie-Hellman or elliptic curve digital signature algorithms, for example) is that of ordinary elliptic curves of almost-prime group order over a prime field.

Elliptic curve parameters for cryptography are generally chosen to avoid attacks via particular structures in elliptic curves, or generic group attacks like the Pohlig-Hellman algorithm that exploit composite group orders. Thus for cryptographically relevant curves, the best cryptanalytic algorithms are the Pollard Rho or parallel collision search algorithms. The expected runtime of these algorithms is well known, and equal to O( √ n) elliptic curve operations, where n is the order of the group, and the O() constant can be made explicit. This runtime is exponential in the size of the public key. Since elliptic curve parameter sizes for cryptography are chosen based on the running time of the best attacks, this is why cryptography using a 256-bit elliptic curve is considered to offer 128 bits of security. The lack of faster attacks for well-constructed curves is why elliptic curve cryptography offers much shorter keys, and thus improved performance, over RSA or finite-field discrete-logarithm based cryptography.

The progress of records for ECDLP cryptanalysis has remained fairly predictable over the past several decades. The current computational record is 114 bits, with progress attributed largely to Moore's law, improvements in hardware, and fast implementations.

Since the current best discrete logarithm algorithms for ECDLP over cryptographically relevant curves are algorithms that apply to any generic cyclic group, it remains an open question whether there is some algorithmic approach that can somehow take advantage of algebraic structure in order to achieve improved cryptanalytic performance. However attempts to mount "index-calculus"-like algorithms (as in NFS) for ECDLP have led to mixed results. No overarching structure like the number field structure in NFS has yet been able to be exploited in this case. Research has proven that ECDLP over composite degree extension fields must be avoided. Beyond this case, some ad hoc algorithms have been proposed. However, bar some claims relying on unconvincing heuristics, they have not been proven to have greater cryptanalytic potential than the generic algorithms.

Over binary fields of prime extension degree, no dramatic progress akin to the quasi-polynomial time algorithm for DLP in GF(2 n ) has appeared. As such, current ECDLP records in this case are also in the same size range as for curves over a prime field.

Pairing-friendly curves are also an interesting special case. By construction, these curves allow one to transfer the elliptic curve DLP to a finite field, whose size is dependent on the curve being chosen. This gives two distinct avenues for cryptanalysis. On the elliptic curve side, the problem is mostly identical to the case of general curves (with mostly identical practical scaling as well), with the exception that automorphisms might reduce the security level by one bit. On the finite field size, recent developments show that some pairing-friendly curve choices might provide a security level that is several bits short of the claimed security level. This area is currently evolving with the practical developments of NFS-like algorithms for moderate-size extension fields (see §2.4).

Prospects for the future

We are at the cusp of a great transition in public-key cryptographic algorithms. All of the computational number theory problems described above that appear to be challenging to solve with a classical computer can, in theory, be broken in polynomial time on a quantum computer. However, it remains an open question whether scaling physical quantum computers to the sizes and error tolerances necessary to run Shor's algorithm can ever be achieved [START_REF]Quantum Computing: Progress and Prospects[END_REF].

Efforts to standardize new "post-quantum" public-key cryptographic algorithms are underway, and will result in algorithm recommendations within the next few years. Future adoption of these algorithms is likely inevitable even if a quantum computer capable of Shor's algorithm is never built. These new algorithms will have a very different mathematical structure from the existing common public-key cryptographic algorithms, opening the door to decades of new research in cryptanalysis.

In the meantime, our existing public-key algorithms will continue to be used, and may have a long half-life when used in conjunction with these newer post-quantum algorithms. Research on classical cryptanalysis will remain relevant because of the long lifetimes of cryptographic algorithms, and because mathematical breakthroughs can result in fast progress. While there is currently no consensus among experts on a timeline for building a quantum computer capable of implementing Shor's algorithm, or whether such a quantum computer will ever be feasible to build, experts do agree that the sheer scale of the engineering effort required is large enough that it would not likely be possible for a single government, say, working alone, to achieve such a feat entirely in secret in a short timeline and take the world by surprise. [START_REF]Quantum Computing: Progress and Prospects[END_REF] In contrast, progress in classical cryptanalysis sometimes requires as little as a single mathematical insight and some software development. We have no evidence that the current running time of the number field sieve is optimal for factoring and discrete logarithm, and as we have seen in the small-characteristic discrete logarithm case, practical mathematical progress can happen rapidly after new insights even after decades of stability, taking even experts by surprise.

Figure 1 :

 1 Figure 1: Main steps of NFS and NFS-DL.

Figure 2 :

 2 Figure 2: RSA factorization and DL computation records.